为啥会WA最后一个点
查看原帖
为啥会WA最后一个点
257173
rish楼主2024/9/19 23:25
#include<bits/stdc++.h>
using namespace std;
const int N = 220;
const int NN = 2e5+10;
string s[N], s2 = "0", x;
int t, j, ans, sum;
int cnt[NN], p[N][NN];
void pre()
{
	j = 0;
	p[t][1] = 0;
	for(int i=1;i<s[t].size();i++)
	{
		while(j>0&&s[t][i+1]!=s[t][j+1]) j = p[t][j];
		if(s[t][i+1]==s[t][j]+1) j++;
		p[t][i+1] = j;
	}
}
void kmp()
{
	for(int k=1;k<=t;k++)
	{
		j = 0;
		for(int i=0;i<s2.size()-1;i++)
		{
			while(j>0&&s[k][j+1]!=s2[i+1]) j = p[t][j];
			if(s[k][j+1]==s2[i+1]) j++;
			if(j==s[k].size()-1)
			{
				cnt[i+1-(s[k].size()-1)+1]++;
				cnt[i+1+1]--;
				j = p[t][j];
			}
		}
	}
}
int main()
{
	while(cin >> x, x!=".")
	{
		s[++t] = "0"+x;
		pre();
	}
	while(cin >> x) s2 += x;
	kmp();
	for(int i=1;i<s2.size();i++)
	{
		sum+=cnt[i];
		if(!sum) break;
		ans++; 
	}
	cout << ans << endl;
	return 0;
}

用了一点前缀和的思想,这样为啥最后一个点会WA

2024/9/19 23:25
加载中...