代码示例 case des author %d cee clu n) ack
poj 2406
Sample Output
- abcd
- aaaa
- ababab
- .
- 1
- 4
- 3
- 题目大意 :
- 此题就可以借助 kmp 的 next数组,因为 next 数组所表示的意义就是当前位置前面的串的最长公共前后缀,所以最后一位中的 next 所存的值就表示其前面的前缀的最长公共部分 是多少 ,用总的长度减去前缀的长度 ,就得出了最小回文的串的长度。
- 代码示例 :
- /*
- * Author: ry
- * Created Time: 2017/10/5 7:29:46
- * File Name: 1.cpp
- */
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <set>
- #include <time.h>
- #include <map>
- using namespace std;
- const int eps = 1e6+5;
- #define ll long long
- char s[eps];
- int next[eps];
- int len;
- void getnext(){
- int i = 0, j = -1;
- next[0] = -1;
- while (i != len){
- if (j == -1 || s[i] == s[j]){
- i++;
- j++;
- next[i] = j;
- }
- else j = next[j];
- }
- }
- int main() {
- while (gets(s) != NULL){
- if (s[0] == ‘.‘) break;
- len = strlen(s);
- getnext();
- int ff = len - next[len];
- if ((len - ff) % ff == 0) printf("%d\n", len/ff);
- else printf("1\n");
- }
- return 0;
- }
- /*
- sadjkghrfkjashioawruiofhasjklryqwodhasnkbfgakjsrhoqwuiyeaskjbtrjksa
- */
kmp-最小子串回文次数
来源: http://www.bubuko.com/infodetail-2337505.html