最后的 s 的转移公式还有问题,实在不知道了,求助
#include<bits/stdc++.h>
using namespace std;
char a[100001] , b[10001];
int lena , lenb , bor[10001];
int pd(int s)
{
for(int i = s ; i <= s+lenb ; i++)
{
if(a[i] != b[i])return i-s+1;
}
return lenb+1;
}
bool pd1(string a , int st1 , int en1 , int st2 )
{
int cha = st2-st1;
for(int i = st1 ; i <= en1 ; i++)
{
if(a[i] != a[i+cha])return false;
}
return true;
}
void border()
{
for(int k = 2 ; k <= lenb ; k++)
{
for(int i = k-1 ; i >= 1 ; i--)
{
if(pd1(b,1,i,k-i+1))
{
bor[k] = i;
break;
}
}
}
}
int main()
{
scanf("%s" , a);
scanf("%s" , b);
lena = strlen(a);
lenb = strlen(b);
for(int i = lena ; i>= 1 ; i--)a[i] = a[i-1];
for(int i = lenb ; i>= 1 ; i--)b[i] = b[i-1];
border();
int s = 1;//从a 的第s个字符遍历起
while(s+lenb-1<=lena)
{
int t = pd(s);
if(t > lenb)//为什么这么判断见pd()
{
cout<<s<<endl;
s++;
continue;
}
else s += t - bor[t];//就这里不会
}
for(int i = 1 ; i<= lenb ; i++) cout<<bor[i]<<" ";
return 0;
}