[USACO 2010 Dec G]Threatening Letter

Consider a 38 letter Moo York Times: THEQUICKBROWNFOXDO GJUMPSOVERTHELAZYDOG from which FJ wants to construct a 9 letter message: FOXDOG DOG These input lines represent a pair of strings: THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG FOXDOGDOG Since "FOXDOG" exists in the newspaper, FJ can cut this piece out and then get the last "DOG" by cutting out either instance of the word "DOG". Thus, he requires but two cuts.

* Line 1: Two space-separated integers: N and M
* Lines 2..?: N letters laid out on several input lines; this is the text of the one copy of the Moo York Times. Each line will have no more than 80 characters.
* Lines ?..?: M letters that are the text of FJ's letter. Each line will have no more than 80 characters.

C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 9308K, 提交时间: 2019-11-02 14:48:57

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+150;
const int kind=26;

int tot=1,las=1;
int ch[maxn*2][kind];
int len[maxn*2],fa[maxn*2],cnt[maxn*2];
inline int read() {
    char c = getchar();
    while (!isalpha(c)) c = getchar();
    return c - 'A';
}

inline int newn(int x){len[++tot]=x;return tot;}
//简化版SAM
void sam_ins(int c){
	int p=las,np=newn(len[las]+1);las=tot;cnt[np]++;
	while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
	if(!p)fa[np]=1;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1) fa[np]=q;
		else{
			int nq=newn(len[p]+1);
			for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i];
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p];
		}
	}
}
int now=1;
int ans=1;
inline void solve(int v){
	if(ch[now][v]){
		now=ch[now][v];
	}
	else{
		++ans;
		now=ch[1][v];
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		sam_ins(read());
	}	
	for(int i=0;i<m;i++){
		solve(read());
	}
	printf("%d\n",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 19ms, 内存消耗: 9108K, 提交时间: 2020-03-02 16:24:00

#include<bits/stdc++.h>
using namespace std;


const int N=1e5+100;


int t[N][26],fa[N],len[N],lst=1,cnt=1;
int ans=1;

void insert(int c)
{
	int p=lst;
	int now=++cnt;
	len[now]=len[lst]+1;
	lst=now;
	for(;p&&t[p][c]==0;p=fa[p]) t[p][c]=now;
	
	if(p==0) fa[now]=1;
	else 
	{
		int q=t[p][c];
		if(len[q]==len[p]+1) fa[now]=q;
		else 
		{
			int nq=++cnt;
			memcpy(t[nq],t[q],sizeof t[0]);
			fa[nq]=fa[q];
			fa[q]=fa[now]=nq;
			for(;p&&t[p][c]==q;p=fa[p]) t[p][c]=nq;
		}
	} 
}
int NOW=1;
void get(int x)
{
	if(t[NOW][x]) NOW=t[NOW][x];
	else 
	{
		ans++;
		NOW=t[1][x];
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	getchar();
	
	char s;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		insert(s-'A');
	}
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		get(s-'A');
	}
	cout<<ans<<endl;
	return 0;
}

详情