F - The Minimum Length HUST - 1010
题目链接: https://vjudge.net/contest/70325#problem/F
题目:
There is a string A. The length of A is Less than 1,000,000. I rewrite it again and again. Then I got a new string: AAAAAA...... Now I cut it from two different position and get a new string B. Then, give you the string B, can you tell me the length of the shortest possible string A.
For example, A="abcdefg". I got abcd efgabcdefgabcdefgabcdefg.... Then I cut the red part: efgabcdefgabcde as string B. From B, you should find out the shortest A.
InputMultiply Test Cases.
For each line there is a string B which contains only lowercase and uppercase charactors.
The length of B is no more than 1,000,000.
- OutputFor each line, output an integer, as described above.Sample Input
- bcabcab
- efgabcdefgabcde
- Sample Output
- 3
- 7
题意: 求最小循环节的长度
思路: kmp 中 n-next[n] 就是最小循环节的长度, 由于现在该题不支持提交, 我就贴一下我写的
- //
- // Created by HJYL on 2019/8/15.
- //
- #include <iostream>
- #include <vector>
- #include <map>
- #include <string>
- #include <queue>
- #include <stack>
- #include <set>
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <cstdlib>
- using namespace std;
- const int maxn=1e6+10;
- char str[maxn];
- int nextt[maxn];
- void getnext()
- {
- int i=0,j=-1;
- nextt[0]=-1;
- int n=strlen(str);
- while(i<n)
- {
- if(j==-1||str[i]==str[j])
- {
- i++,j++;
- if(str[i]!=str[j])
- nextt[i]=j;
- else
- nextt[i]=nextt[j];
- } else
- j=nextt[j];
- }
- }
- int main()
- {
- //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text","r",stdin);
- while(~scanf("%s",str))
- {
- getnext();
- int len=strlen(str);
- printf("%d\n",len-nextt[len]);
- }
- return 0;
- }
[kuangbin 带你飞] 专题十六 KMP & 扩展 KMP & Manacher F - The Minimum Length HUST - 1010 (kmp 循环节)
来源: http://www.bubuko.com/infodetail-3157001.html