義塚OJ P5018 Oulipo

义冢 OJ P5018 Oulipo#

説明#

2 つの文字列 W と T が与えられたとき、T の中にいくつの W の部分文字列があるかを求めます。

入力#

最初の行はデータの組数です。

各データは 2 行で、W と T を表し、パターン文字列と元の文字列です。

出力#

各データに対して、各行に 1 つの数を出力し、マッチ数を示します。

入力例 1#

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

出力例 1#

1
3
0

ヒント#

1 ≤ |W| ≤ 10,000 (ここで |W| は文字列 W の長さを示します)。 |W| ≤ |T| ≤ 1,000,000.

実装#

KMP の板子問題

ただブログを更新するために板子を書くだけです。。。。

コード#

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int MAXN=1e6+5;

int nxt[MAXN]={0};

void setNext(string s);
int kmp(string s1,string s2);

int n;

int main()
{
	cin>>n;
	string s1,s2;
	for(int i=1;i<=n;++i)
	{
		cin>>s1>>s2;
		setNext(s1);
		cout<<kmp(s2,s1)<<endl;
	}
	
	return 0;
}
void setNext(string s)
{
	memset(nxt,0,sizeof(nxt));
	nxt[0]=-1;
	int sl=s.size();
	for(int i=1;i<sl;++i)
	{
		int t=nxt[i-1];
		while(s[t+1]!=s[i]&&t>=0)
		{
			t=nxt[t];
		}
		if(s[t+1]==s[i])
		{
			nxt[i]=t+1;
		}
		else
		{
			nxt[i]=-1;
		}
	}
}
int kmp(string s1,string s2)
{
	int i=0,j=0;
	int sl1=s1.size(),sl2=s2.size();
	int cnt=0;
	while(i<sl1)
	{
		if(s1[i]==s2[j])
		{
			++i;
			++j;
			if(j==sl2)
			{
				++cnt;
				j=nxt[j-1]+1;
			}
		}
		else
		{
			if(j==0)++i;
			else j=nxt[j-1]+1;
		}
	}
	return cnt;
}