Mean:
給你一個字元串,讓你在後面加盡量少的字元,使得這個字元串成為一個重複串。
例:
abca---添加bc,成為abcabc
abcd---添加abcd,成為abcdabcd
aa---無需添加
analyse:
經典的求最小循環節。
首先給出結論:一個字元串的最小循環節為:len-next[len]。
證明:
舉個例子:abcabc的最小循環節是abc,abcda的最小循環節是abcd,abbab的最小循環節是abb。
看出點什麼端倪沒?
證明開始:
-----------------------
k m x j i
由上,next[i]=j,兩段紅色的字元串相等(兩個字元串完全相等),s[k....j]==s[m....i]
設s[x...j]=s[j....i] ,記為:(xj=ji)
則可得,以下簡寫字元串表達方式:
kj=kx+xj;
mi=mj+ji;
因為xj=ji,是以kx=mj,如下圖所示
-------------
-------------
k m x j
看到了沒,此時又重複上面的模型了,kx=mj,是以可以一直這樣遞推下去。
是以可以推出一個重要的性質len-next[len]為此字元串的最小循環節。
另外如果len%(len-next[len])==0,此字元串的最小周期就為len/(len-next[i])。
有了這個結論,這題就好做多了。注意判斷一下是否原串就是一個重複串。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-27-21.10
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN=100010;
char s[MAXN];
int Next[MAXN];
void getNext()
{
Next[0]=0;
int s_len=strlen(s);
for(int i=1,k=0;i<s_len;++i)
{
while(s[i]!=s[k]&&k) k=Next[k-1];
if(s[i]==s[k]) ++k;
Next[i]=k;
}
}
int main()
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
scanf("%d",&t);
while(t--)
scanf("%s",s);
getNext();
int s_len=strlen(s);
int min_cycle=s_len-Next[s_len-1];
if(min_cycle!=s_len && s_len%min_cycle==0)
{
puts("0");
}
else
int need_add=min_cycle-Next[s_len-1]%min_cycle;
printf("%d\n",need_add);
return 0;