【P2353 背单词】题解

题目链接

首先我们发现单词个数，也就是 \(m\) 很小，这启示着我们不需要用到什么神仙字符串算法，可以暴力kmp。

对于每个单词与原串做kmp匹配，用前缀和记录能匹配成功的，每次询问 \(O(m)\) 回答即可。

时间复杂度：\(O(m\times(n+q))\)

Code

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 1000020
int n, m, i, j, k; 
char s[N], c[N]; 
int p[N], sum[12][N], len[12]; 
int q, l, r, ans; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin);
//	freopen("tiaoshi.out", "w", stdout);
	m=read(); q=read(); 
	scanf("%s", s+1); n=strlen(s+1); 
//	p[1]=0; 
//	for(i=2, j=0; i<=n; ++i)
//	{
//		while(j&&s[i]!=s[j+1]) j=p[j]; 
//		if(s[i]==s[j+1]) ++j; 
//		p[i]=j; 
//		printf("p[%lld]=%lld\n", i, p[i]); 
//	}
//	printf("-----\n"); 
	for(i=1; i<=m; ++i)
	{
		scanf("%s", c+1); len[i]=strlen(c+1); 
		memset(p, 0, sizeof(p)); 
		k=0; p[1]=0; 
		for(j=2; j<=len[i]; ++j)
		{
			while(k&&c[k+1]!=c[j]) k=p[k]; 
			if(c[k+1]==c[j]) ++k; 
			p[j]=k; 
//			printf("%lld ", p[k]); 
		}
		k=0; 
		for(j=1; j<=n; ++j)
		{
			sum[i][j]=sum[i][j-1]; 
			while(k&&c[k+1]!=s[j]) k=p[k]; 
			if(c[k+1]==s[j]) ++k; 
			if(k==len[i]) ++sum[i][j]; 
//			printf("sum[%lld][%lld]=%lld\n", i, j, sum[i][j]); 
		}
//		printf("\n"); 
	}
	while(q--)
	{
		l=read(); r=read(); 
		for(i=1, ans=0; i<=m; ++i)
			ans+=max(0, sum[i][r]-sum[i][min(n, l+len[i]-1-1)]); 
//			ans+=max((long long)0, sum[i][r]-sum[i][l+len[i]-1-1]); 
		printf("%d\n", ans); 
	}
	return 0;
}