P*******b
发帖数: 1001 | 1 就是有一个byte流，从开始读，读到第一个
回文的时候就停。例如，
第一次读4
下一次读1
下一次读3
下一次读3
下一次读1
下一次读4，这个时候停。
要求线性时间。
thanks |
p*****2
发帖数: 21240 | |
g*******s
发帖数: 2963 | 3 这个回文必须是从头开始么？不然读到第二个3就应该返回[3,3]了？
还是说第一个回文with max length as possible? |
p*****2
发帖数: 21240 | 4
从头开始
【在 g*******s 的大作中提到】
: 这个回文必须是从头开始么？不然读到第二个3就应该返回[3,3]了？
: 还是说第一个回文with max length as possible?
|
l*****a
发帖数: 14598 | 5 不像
【在 p*****2 的大作中提到】
: rolling hash?
|
f*****e
发帖数: 2992 | 6 max palindrome substring的变体吧。
【在 l*****a 的大作中提到】
: 不像
|
g*******s
发帖数: 2963 | 7 最土的On方法，就是设两个pivot代表中间的对称点. 这个点可以是个区间。基本就两
种情况比如 4311134，对称点就是111，或者43134对称点就是313，然后从这个对称区
间往两边扩展match，一旦发现不match就放弃当前pivot。
#include
#include
using namespace std;
vector findFristPal(vector& src)
{
int srcSize = src.size();
if (srcSize==0) return vector();
if (srcSize<=1) return vector(src[0],1);
bool isMatching = false;
int pivotLeft = 0;
int pivotRight = 0;
for (int i=1; i
{
if (!isMatching)
{
if(src[i]==src[i-1])
{
isMatching = true;
pivotLeft = i-1;
pivotRight = i;
}
else if (i>1 && src[i]==src[i-2])
{
isMatching = true;
pivotLeft = i-2;
pivotRight = i;
}
if (isMatching && i==srcSize-1)
return vector(src.begin(), src.begin()+i+1);
}
else
{
// extend pivot if possible
if (i==pivotRight+1 && src[i] == src[pivotRight])
{
pivotRight++;
continue;
}
// give up the current pivots if found unmatch
if(src[i]!=src[pivotLeft-(i-pivotRight)])
{
isMatching=false;
continue;
}
// output if the match of 1st element found
if(i-pivotRight == pivotLeft)
{
return vector(src.begin(), src.begin()+i+1);
}
}
}
return vector();
} |
l*****a
发帖数: 14598 | 8 你这种做法对stream/array的处理有区别吗？
【在 g*******s 的大作中提到】
: 最土的On方法，就是设两个pivot代表中间的对称点. 这个点可以是个区间。基本就两
: 种情况比如 4311134，对称点就是111，或者43134对称点就是313，然后从这个对称区
: 间往两边扩展match，一旦发现不match就放弃当前pivot。
: #include
: #include
: using namespace std;
: vector findFristPal(vector& src)
: {
: int srcSize = src.size();
: if (srcSize==0) return vector();
|
p*****2
发帖数: 21240 | 9
我感觉可以，线性时间可解
【在 l*****a 的大作中提到】
: 不像
|
