为什么我的思路和别人都不一样??!!
查看原帖
为什么我的思路和别人都不一样??!!
524906
刘辰雨楼主2021/11/19 08:40

最后的 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;
} 
2021/11/19 08:40
加载中...