LPS
今天是Admis算法讨论班第一次课，回顾了一下最长回文子串(LPS)问题以及KMP，LPS的马拉车(瞿神起的中文名)算法 是比较难的算法。
之前看了邹博PPT写了一次，一次AC，但是第一次写是比较卡的。
后来今天写发现很不熟练，而且debug了半天，然后发现里面if漏掉了判断i在mx左右就去判断mx-i和P[j]的关系。代码如下：
void LPS()//2n+1
{
P[0]=1;//len at least 1
id=0, mx=id+P[id], maxp=0,maxi=0;
int len=newstr.size();
for(int i=1;i<=len-1;i++)
{
j=2*id-i;
if(mx>i)
{
if(mx-i>=P[j])
P[i]=P[j];
else
{
P[i]=mx-i;
}
}
else
P[i]=1;
while(i+P[i]<=len-1 && i+P[i]>=0 && i-P[i]<=len-1 && i-P[i]>=0 && newstr[i+P[i]]==newstr[i-P[i]])
P[i]++;
if(mx<i+P[i])
{
id=i;
mx=id+P[id];
}
if(maxp<P[i]-1)
maxp=P[i]-1,maxi=i;
}
//for(int i=0;i<=len-1;i++)
// cout<<P[i]<<" ";
}
void Extend()
{
string jing="#";
newstr="#";
for(int i=0;i<str.size();i++)
{
newstr+=str[i];
newstr+=jing;
//newstr+=str[i];
//newstr+="#";
}
//cout<<newstr<<endl;
}
后来写了一个朴素的枚举中心位置，如果每次等到确定了位置再去判断回文串就是O(n^3), 其实可以每一次extend一个字符都判断是否回文了，这样还是O(n^2),代码如下
string longestPalindrome_n2_enum(string s)
{
str=s;
Extend();
int maxextlen=0, centeri=0,extlen;
int len=newstr.size();
for(int i=0;i<len;i++)
{
extlen=0;
while(i-extlen>=0 && i+extlen<=len-1 && newstr[i-extlen]==newstr[i+extlen])
extlen++;
extlen--;
if(maxextlen<extlen)
centeri=i,maxextlen=extlen;
}
string withjing=newstr.substr(centeri-maxextlen, 2*maxextlen+1);
string result;
for(int i=0;i<withjing.size();i++)
{
if(withjing[i]!='#')
result+=withjing[i];
}
return result;
}
今天肥站提出需要修改一下最后输出结果的处理，直接定位原串位置，
似乎奇偶串要分开处理，于是以下代码
if(newstr[maxi]==’#’)
return str.substr((maxi-1)/2-(P[maxi]-1)/2+1,P[maxi]-1);
else
return str.substr(maxi/2-(P[maxi]-1)/2,P[maxi]-1);
后来站站说只有一个语句，似乎是的。
return str.substr(maxi/2-(P[maxi]-1)/2,P[maxi]-1);
今天豆豆提到了DP算法，我之前看到过，但是一位是上面的enum算法，后来看了发现不是的，DP(i,j)=DP(i+1,j-1) if(s[i]=s[j])
于是打算写一下。虽然LeetCode一次AC，因为时间卡的不严，像hihocoder第一题必须是最优的马拉车算法，记得微博上cici埕好像也是直接一A，只是一开始编译器选错了。
里面需要注意的是base和递推关系，这是DP的关键。这里递推的长度是间隔2的，所以base必须是长为1和2的状态都要算出来，然后奇偶交替递推。
然后就是递推状态之间是长度小的决定长度大的，因此外层for一定要长度从小到大过去，和矩阵链一样。第一次run又挂了， 又是二维数组开打了，每次都被这个吓得代码没自信了。
string longestPalindrome_n2_dp(string s)
{
int maxi=0, maxj=0,n=s.size();
for(int i=0;i<=n-1;i++)
memset(dp[i],0,sizeof(dp[i]));
for(int i=0;i<=n-1;i++)
dp[i][i]=1;//len=1
for(int i=0;i<=n-2;i++)
{
if(s[i]==s[i+1])//len=2
dp[i][i+1]=1,maxi=i,maxj=i+1;
}
for(int len=3;len<=n;len++)
{
for(int i=0;i<=n-1;i++)
{
int j=i+len-1;
if(j>=n)
break;
if(s[i]==s[j])
dp[i][j]=dp[i+1][j-1];
if(dp[i][j])
maxi=i,maxj=j;
}
}
return s.substr(maxi, maxj-maxi+1);
}
上面的代码都在LeetcodeAC了，再加上暴力的枚举位置，外加结束再判断回文串的O(n^3), 一共是豆豆所说的4种算法。提倡一题多解，训练代码能力。