int MinimumRepresentation(int *s, int l)
{
int i,j,k;
i=0;j=1;k=0;
while(i<l&&j<l)
{
k=0;
while(s[i+k]==s[j+k]&&k<l) k++;
if(k==l) return i;
if(s[i+k]>s[j+k])
if(i+k+1>j) i=i+k+1;
else i=j+1;
else if(j+k+1>i) j=j+k+1;
else j=i+1;
}
if(i<l) return i;
else return j;
}
void getFail(char* P, int* f)
{
int m=strlen(P);
f[0] = 0;
f[1] = 0;
for(int i = 1; i < m; i++)
{
int j = f[i];
while(j && P[i] != P[j])
{
j = f[j];
}
f[i + 1]=P[i]==P[j]?j+1:0;
}
}
我们可以看到的是fail数组最后知道了fail[m]的结果,所以求重复子串的时候就是
if(j==m) ans++,就行了
int find(char* T, char*P, int*f)
{
int ans;
int m = strlen(P);
int temp=2*n;
getFail(P, f);
int j = 0;
for(int i = 0; i < temp; i++)
{
while(j && P[j] != T[i])
{
j = f[j];
}
if(P[j] == T[i])
{
j++;
}
if(j == m)
{
if(i-m+1<n) ans=i-m+1;
else return ans;
//j=f[j-1];
//i--;
}
}
return ans;
}