Daily programming challenge

Write a program that finds the longest palindromic substring of a given string.

pwonmcwq should give you NULL
re109901e should give you e109901e
aspsdeqqedi3elmssmle3i should give you 3elmssmle3i

Other urls found in this thread:

fun-with-words.com/palindromes.html
twitter.com/NSFWRedditGif

We're not doing your homework

static String psub( String string) {
if( string == null || string.equals("")) return null;
String largest = string.substring(0, 1);
for( int i=0; i

It is your homework though. You are free to use your language :)

can you tell me what palindromic means

fun-with-words.com/palindromes.html

dug through my old code

feast your eyes on this beaut
private static string Reverse(string input) => string.Concat(input.Reverse().Select(c => c));

private static string FindPalindromes(string input) {
string longestpal = default(string);
for (int i = 0; i < input.Length; i++) {
for (int j = input.Length - i; j > 1; j--) {
string substring = input.Substring(i, j);
//mess ahead
bool even = substring.Length % 2 == 0 &&
substring.Substring(0, substring.Length / 2) ==
Reverse(substring.Substring(substring.Length / 2, substring.Length / 2));
bool odd = substring.Length % 2 != 0 &&
substring.Substring(0, substring.Length / 2) ==
Reverse(substring.Substring(substring.Length / 2 + 1, substring.Length / 2));
bool replaceable = longestpal == default(string) || longestpal.Length < substring.Length;
//mess over
if (even && replaceable) {
longestpal = substring;
}
else if (odd && replaceable) {
longestpal = substring;
}
}
}
return longestpal;

>private static string Reverse(string input) => string.Concat(input.Reverse().Select(c => c));
Jesus christ

import Data.List

f :: Eq a => [a] -> [[a]]
f xs
| xs == [] = []
| xs == (reverse xs) = [xs]
| otherwise = nub $ (f $ init $ xs) ++ (f $ tail $ xs)

g :: Eq a => [[a]] -> [[a]]
g xs = [x | x [a] -> [[a]]
h = g . f

I did this a few years ago. This is fast. The general idea is to walk along the string and try expand a subsection out on both sides while it is a valid palidrome.
package main

import (
"fmt"
"io/ioutil"
)

// " \t\r\n"
var spaces = map[byte]bool{ 32: true, 9: true, 10: true, 13: true }


func longestPalindrome(text []byte) ([]byte, int, int) {

textlen := len(text)
maxlen := 0
maxlow := 0
maxhigh := 0
low := 0
high := 0

var current byte
var previous byte

for i := range text {

// lowercase char
if text[i] > 64 && text[i] < 91 { text[i] += 32 }

// Handle both odd and even-length palindromes
for j := i; j < i + 2 && j < textlen; j ++ {

low = i
high = j

// Expand while the subregion is a valid palindrome
for text[low] == text[high] {

// discount multiple spaces
current = text[low]
if spaces[current] && spaces[previous] { break }

// If longest found, update
if high - low > maxlen {
maxlow = low
maxhigh = high
maxlen = maxhigh - maxlow
}

// update prev
previous = current

// expand indexes
if low > 0 { low -- } else { break }
if high < textlen - 1 { high ++ } else { break }
}
}
}

maxhigh ++; if maxhigh > textlen { maxhigh = textlen }

return text[maxlow : maxhigh], maxlow, maxhigh
}


func main() {

text, _ := ioutil.ReadFile("war_and_peace.txt")

str, _, _ := longestPalindrome(text)

fmt.Println(string(str))
fmt.Println(str)
}

couldn't you do this with regex?

even if you could, it would take forever to run

OP, you really should be writing a solution before making this thread.
All of your sample outputs are wrong.

char *palindrome(const char *str)
{
unsigned len = strlen(str);
unsigned i, j;
for (i = len; i > 1; --i) /* substr length */
{
for (j = 0; i + j 0; --k) /* reverse */
pal[idx++] = str[j + k];
if (!memcmp(pal, &str[j], i))
return pal;
else
free(pal);
}
}
return NULL;
}

me on the right

string revert(const string& input)
{
string ret = "";
for (int i = input.size()-1; i>=0; --i) {
ret += input[i];
}
return ret;
}

string palindrome(const string& input)
{
string reverse = revert(input);
vector first;
vector second;
for (int i = 0; i < input.size(); ++i) {
for (int j = i; j < input.size(); ++j) {
string newitem = "";
string newitem2 = "";
for (int k = i; k < j + 1; ++k) {
newitem += input[k];
newitem2 += reverse[k];
}
first.push_back(newitem);
second.push_back(newitem2);
}
}
string longest = "";
for (int i = 0; i < first.size(); ++i) {
for (int j = 0; j < second.size(); ++j) {
if (first[i] == second[j] && first[i].size() > longest.size()) {
longest = first[i];
}
}
}
return longest;
}


My solution is way too expensive, but I think its nice because its easy to follow. (Except maybe the nested loops.)

No.

Don't forget about the palindromes of odd length, people. This simple solution works nicely when palindromes have alternating letters but degrades to O(n^2) on rows of same letters. Also walking the array twice could be avoided but eh.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace palindromeFinder
{
class Program
{
static void Main(string[] args)
{
var src = Console.ReadLine();
int maxl = 0;
var pal="NULL";
for(int i = 0; i < src.Length-1; i++)//even
{
if (src[i] == src[i + 1])
{
int l = 1;
while (i - l + 1 >= 0 && i + l < src.Length && src[i - l + 1] == src[i + l])
l++;
l--;
if (l > maxl)
{
maxl = l;
pal = src.Substring(i - l + 1, l * 2);
}
}
}
for (int i = 1; i < src.Length - 1; i++)//odd
{
if (src[i-1] == src[i + 1])
{
int l = 1;
while (i - l >= 0 && i + l < src.Length && src[i - l] == src[i + l])
l++;
l--;
if (l > maxl)
{
maxl = l;
pal = src.Substring(i - l , l * 2 +1);
}
}
}
Console.WriteLine(pal);
}
}
}

Your thread sucks!
Birdmin Stabber was better.

Fixed a subtle error + don't spam substringing anymore.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace palindromeFinder
{
class Program
{
static void Main(string[] args)
{
var src = Console.ReadLine();
int maxl = 0,maxi=0;
for(int i = 0; i < src.Length-1; i++)//even
{
if (src[i] == src[i + 1])
{
int l = 1;
while (i - l + 1 >= 0 && i + l < src.Length && src[i - l + 1] == src[i + l])
l++;
l--;
if (l*2 > maxl)
{
maxl = l*2;
maxi = i;
}
}
}
for (int i = 1; i < src.Length - 1; i++)//odd
{
if (src[i-1] == src[i + 1])
{
int l = 1;
while (i - l >= 0 && i + l < src.Length && src[i - l] == src[i + l])
l++;
l--;
if (l*2+1 > maxl)
{
maxl = l*2+1;
maxi = i;
}
}
}
Console.WriteLine((maxl==0)?"NULL": src.Substring(maxi-maxl/2+1-maxl%2,maxl));
}
}
}

Birdmin stabber problems were elementary grade

So is this si oS.

Rate my solution
void Main()
{
Debug.Assert((GetMaxPalindrome("re109901e") == "e109901e"), "First Test");
Debug.Assert(GetMaxPalindrome("aspsdeqqedi3elmssmle3i") == "i3elmssmle3i", "Second Test");
}

string GetMaxPalindrome(string str)
{
string currentMaxPal = string.Empty;

for (int i = 0; i < str.Length; i++)
{
string pal = GetPalindrome(str, i);
if (pal.Length > currentMaxPal.Length)
currentMaxPal = pal;
}

return string.IsNullOrEmpty(currentMaxPal) ? null : currentMaxPal;
}

string GetPalindrome(string str, int index)
{
string currentPalindrome = string.Empty;
int counter = 0;

while (index - counter >= 0 && index + counter + 1< str.Length)
{
char left = str[index - counter],
right = str[index + counter + 1];

if (left != right)
break;

currentPalindrome = left + currentPalindrome + right;

counter++;
}

return currentPalindrome;
}

org 0x100
use16

xor ch, ch
mov cl, [0x80]
jcxz exit
push cx
mov di, r
mov si, 0x81
add si, cx
@@: std
lodsb
cld
stosb
loop @b
pop cx
xor bp, bp
search:
mov si, 0x81
lea di, [r+bp]
@@: push di
push si
push cx
repe cmpsb
je found
pop cx
pop si
pop di
inc si
dec di
cmp di, r
jae @b
dec cx
inc bp
jcxz exit
jmp search
found:
pop bp
pop dx
add bp, dx
mov byte [bp+1], '$'
mov ah, 0x09
int 0x21
exit:
mov ax, 0x4c00
int 0x21

r rw 0

Improved to detect both even and odd length palindromes
void Main()
{
Debug.Assert(GetMaxPalindrome("re109901e") == "e109901e", "First Test");
Debug.Assert(GetMaxPalindrome("aspsdeqqedi3elmssmle3i") == "i3elmssmle3i", "Second Test");
Debug.Assert(GetMaxPalindrome("re10901e") == "e10901e", "Third Test");
}

string GetMaxPalindrome(string str)
{
string currentMaxPal = string.Empty;

for (int i = 0; i < str.Length; i++)
{
string pal;

pal = GetPalindrome(str, i, false);
if (pal.Length > currentMaxPal.Length) currentMaxPal = pal;

pal = GetPalindrome(str, i, true);
if (pal.Length > currentMaxPal.Length) currentMaxPal = pal;
}

return currentMaxPal;
}

string GetPalindrome(string str, int index, bool even)
{
string currentPalindrome = string.Empty;
int counter = 0,
offset = even ? 1 : 0;

while (index - counter >= 0 && index + counter + offset < str.Length)
{
char left = str[index - counter],
right = str[index + counter + offset];

if (left != right)
break;

currentPalindrome = left + currentPalindrome;
if (even || counter > 0) currentPalindrome += right;

counter++;
}

return currentPalindrome;
}

>It's another episode of ASM being less verbose than C

> no main method
> not using maximumBy
0/10 tbqh senpai
import Data.List
import Data.Ord
import System.Environment

f xs
| xs == [] = []
| xs == reverse xs = [xs]
| otherwise = nub $ (f $ init xs) ++ (f $ tail xs)

g xs = fst . maximumBy (comparing snd) $ zip xs $ map length xs

main = do s

I guess I should post easy problems

This is an easy problem >ecks d

std::string find_palindrome(std::string s)
{
for (auto l = s.length(); l > 1; --l)
for(auto i = 0; s.begin() + l + i - 1 != s.end(); ++i)
if (std::equal(s.begin() + i, s.begin() + l + i, s.rend() - l - i))
return std::string { s.begin() + i, s.begin() + l + i };
return { };
}

(import (ice-9 rdelim) (srfi srfi-26))

(define (longest-palindrome str)
(define (longest-palindrome-right str)
(cond (( (string-length x) (string-length y))))))
(longest (map (compose longest-palindrome-right (cute string-drop str ))
(iota (- (string-length str) 1)))))

(simple-format #t "~S\n" (longest-palindrome (read-line)))

int CheckPalindrome(char str[])
{
int i = 0, len, curlen = strlen(str)-2;

if(strlen(str)+1&1)
{
len = strlen(str)/2 - 1;
}
else
{
len = strlen(str)/2;
}

for(;istrlen(current))
{
strcpy(current, tempstr);
current[j-i-1] = '\n';
}
}
}
}
return strlen(current)>3?current:"NULL";
}


Schoolar way

Why do you have so many calls to strlen?
Store it once, it's not like it's going to change again unless you purposefully reallocated it.

len -= (len = strlen(str) / 2) & 1; /* check odd */

You are right, I should have stored it, but cba-d went to do the "workd" as fast as possible, and this was just to play in C after long time, I prefer C# any day.

Also, where the fuck did you learn C?
Your style is nasty, I hope you don't write C# like this.

I don't write the C# as close.
I just wanted to check myself if I still know how to do those nasty malloc's lol or string copying. God I hate C.

>being a casual

you, you I like

doing it for the lulz
#include
#include
void erase(char* in, std::size_t l) {
for (int i=0;i

I just realized I didn't even need to memcpy the substring because i'm clobbering it anyway.

char *palindrome(const char *str)
{
unsigned len = strlen(str);
unsigned i, j;
for (i = len; i > 1; --i) /* substr length */
{
for (j = 0; i + j 0; --k) /* reverse */
pal[idx++] = str[j + k - 1];
if (!memcmp(pal, &str[j], i))
return pal[i] = '\0', pal;
else
free(pal);
}
}
return NULL;
}

what language are you trying to write?

its c++ but doing c strings for the lulz

OP this shit was too easy, you made it too similar to the last one.

#include

std::string longest_palindromic_substr(std::string str)
{
std::string ret = "";
for (unsigned i = 0; i < str.length() - 3; i++) {
for (int j = i + 3; j < str.length(); j++) {
std::string temp = str.substr(i, j - i + 1);
if (std::equal(temp.begin(), temp.end(), temp.rbegin())
&& temp.length() > ret.length()) {
ret = temp;
}
}
}
if (ret.empty()) return "NULL";
return ret;
}


I like this one.

Bored so I optimized it.
static String psubOp( String string) {
if( string == null || string.equals("")) return null;
int offset = 0;
int len = 1;

for( int i=1; i< string.length()-(len+1)/2; ++i) {
int grow;
// Odd
for( grow=1; i - grow >= 0 && i+grow < string.length() && string.charAt(i-grow) == string.charAt(i+grow); ++grow);
if( grow + grow - 1 >len) {
offset = i - grow + 1;
len = grow + grow - 1;
}
// Even
for( grow=0; i-grow>=0 && i+grow+1 < string.length() && string.charAt(i-grow) == string.charAt(i+grow+1); ++grow);
if( (grow)*2 > len) {
offset = i - grow+1;
len = grow*2;
}
}

return string.substring(offset, offset+len);
}