电子商务网站毕业论文/搜索引擎优化的内容包括

对给定的字符串(1000),输出最长回文子串的长度.
数据范围只有1000,其实可以直接暴力O(n^2).
学习一下O(n)的manacher.

manacher利用了字符串中各回文串之间的联系:若S为T的子串,T是回文串,则S回文等价于S’回文,其中S’是S在T中的对称子串.
从左向右枚举依次回文串中心,如果中心位置不在已知的回文串内部,则暴力求此中心的回文串.并将这个回文串设为已知的回文串.
如果中心位置在已知回文串内部,那么查询它的对称位置,如果对称位置没有触碰或超过已知回文串左边界,那么这个位置的答案就是对称位置的答案.
否则,从右边界开始暴力求出答案,然后将这个回文串设为已知回文串.

manacher有一个很重要的预处理过程,将字符串首尾加一个不常用字符$,然后在每两个字符之间再加一个不常用字符#.这样做的目的是避免考虑边界,强行让相邻字符不同使得所有回文串都以字符为中心,瞬间简化了问题.
得到的答案是一个数组,存储了每个位置向一个方向的回文串延伸次数,注意这个长度是处理后的长度,也就是原串中回文串的长度.

写完之后参考了zbh的ppt里的代码,做了一些小的修改.

/* LittleFall : Hello! */
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read();
inline void write(int x);
const int M = 1000256;
char s[M], s2[M * 2 + 1];
int ans[M * 2 + 1];
int manacher()
{int id = 0, pos = 0, rig = 0, ret = 0;//索引,矩形位置,矩形右边界,结果s2[0] = '$';do s2[2 * id + 1] = '#', s2[2 * id + 2] = s[id];while (s[id++]);ans[0] = 0;for (id = 1; s2[id]; id++){ans[id] = id >= rig ? 0 : min(rig - id, ans[pos * 2 - id]);while (s2[id + ans[id] + 1] == s2[id - ans[id] - 1]) ans[id]++;if (id + ans[id] > rig) rig = id + ans[id], pos = id;ret = max(ret, ans[id]);}return ret;
}int main(void)
{
#ifdef _LITTLEFALL_freopen("in.txt", "r", stdin);
#endif//std::cin.sync_with_stdio(false);cin.getline(s, M);printf("%d\n", manacher() );return 0;
}inline int read()
{int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void write(int x)
{if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');
}

String-manacher 加入我的模板库!