广州微网站建设案例,一键生成ppt免费,erp软件多少钱一套,立方米网站建设题意#xff1a;给一个字符串S#xff0c; 求出所有前缀pre#xff0c;使得这个前缀也正好是S的后缀。 输出所有前缀的结束位置。
就是求前缀和后缀相同的那个子串的长度 然后从小到大输出,主要利用next数组求解。
例如 “ababcababababcabab”#xff0c; 以下这些前缀…题意给一个字符串S 求出所有前缀pre使得这个前缀也正好是S的后缀。 输出所有前缀的结束位置。
就是求前缀和后缀相同的那个子串的长度 然后从小到大输出,主要利用next数组求解。
例如 “ababcababababcabab” 以下这些前缀也同时是S的后缀
ab 位置2
abab 位置4
ababcabab 位置9
ababcababababcabab 位置 18
分析与总结
这题关键在于对KMP的失配函数的理解。只要真正理解了那么做出来完全不成问题。
next[i]的意义就是前面长度为i的字串的【前缀和后缀的最大匹配长度】
下面是后来在网上找的一个图片很形象. e.g.
i01 2 345678 9 1011121314151617 18 dpab a bcabab a babcabab /0 next-10 0 120123 4 34345678 9 Out: 2 4 9 18 由于子串既是S的前缀又是后缀所以除去字符串本身长度18外次长的为在字符串结束符‘\0’处求得的next数组值9 此时S的前缀为 ababcabab(012345678)S的后缀为 ababcabab(9-17)。接着找第三长的既是S的前缀又是S后缀的子串。 如果找next[17]处的值8则不满足是S后缀的要求因为17本身的字符是被排除在外的10-16亦是同理。 而对于9之前的子串有next[18]知既是S的前缀又是S的后缀。而next[9]的值4指明了位置在9前的子串的前后缀长度为4 而该子串包含在S的前缀中所以该子串的后缀也包含在S的前缀中而S的前缀又是S的后缀所以该子串的后缀也是S的后缀。 依次往前直到满足条件的子串长度为0为止。
题目
The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm: Step1. Connect the fathers name and the mothers name, to a new string S. Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S). Example: Fatherala, Motherla, we have S alala alala. Potential prefix-suffix strings of S are {a, ala, alala}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)
Input
The input contains a number of test cases. Each test case occupies a single line that contains the string S described above. Restrictions: Only lowercase letters may appear in the input. 1 Length of S 400000.
Output
For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new babys name.
Sample Input
ababcababababcabab
aaaaaSample Output
2 4 9 18
1 2 3 4 5
AC代码
#includestdio.h
#includestring.h
using namespace std;
const int M4e510;
char dp[M];
int s[M],e[M];
void f(int x)
{memset(s,0,sizeof(s));int i0;int j-1;s[0]-1;while(ix){if(j-1||dp[i]dp[j])s[i]j;else js[j];}
}
int main()
{while(~scanf(%s,dp)){memset(e,0,sizeof(e));int xstrlen(dp);f(x);int b0,k,a0,i,flag0;ix;while(i!-1){e[a]i;is[i];if(i0)break;}for(ia-1; i1; i--)printf(%d ,e[i]);printf(%d\n,e[0]);}return 0;
}
