KMP 字典树

KMP

KMP是三个科学家的名字的缩写,KMP能够高效的实现字符串匹配问题。

接下来看几道栗子吧

KMP

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

1≤N≤10^5
1≤M≤10^6

输入样例：

3
aba
5
ababa

输出样例：

0 2

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

char s1[N],s2[N];
int ne[N];

void solve()
{
	int n,m;

	cin >> n >> s1 + 1;
	cin >> m >> s2 + 1;

	for(int i = 2, j = 0; i<=n; i++)
	{
		while(j&&s1[j+1]!=s1[i]) j=ne[j];
		if(s1[j+1]==s1[i]) j++;
		ne[i]=j;
	}

	for(int i = 1,j = 0; i<=m; i++)
	{
		while(j&&s1[j+1]!=s2[i]) j=ne[j];
		if(s1[j+1]==s2[i]) j++;
		if(j==n)
		{
			cout << i-j <<' ';
			j = ne[j];
		}
	}
}

signed main()
{
	solve();

	return 0;
}

字典树

字典树是高效存储和查询字符串的工具。

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 x；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗10^4

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int tr[N][27];
int idx;
int cnt[N];

void insert(string s)
{
	int p = 0;
	for(int i = 0; i<s.size(); i++)
	{
		char t = s[i]-'a';
		if(!tr[p][t]) tr[p][t]=++idx;
		p = tr[p][t];
	}
	cnt[p]++;
}

int que(string s)
{
	int p = 0;
	for(int i = 0; i<s.size(); i++)
	{
		char t = s[i]-'a';
		if(!tr[p][t]) return 0;
		p = tr[p][t];
	}

	return cnt[p];
}

void solve()
{
	int n;
	cin >> n;

	for(int i = 1; i<=n; i++)
	{
		char a;
		cin >> a;

		if(a=='I')
		{
			string s;
			cin >> s;
			insert(s);
		}
		else
		{
			string s;
			cin >> s;

			cout << que(s)<<endl;
		}
	}
}

signed main()
{
	solve();

	return 0;
}

再看一道例题

在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1～AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10^5
0≤Ai<2^31

输入样例：

3
1 2 3

输出样例：

3

#include<iostream>

using namespace std;

const int N = 4e6 + 10;

int a[N];
int tr[N][3];
int idx;

void insert(int x)
{
	int p = 0;
	for(int i = 30; i>=0; i--)
	{
		int t = x>>i&1;
		if(!tr[p][t]) tr[p][t]=++idx;
		p=tr[p][t];
	}
}

int que(int x)
{
	int p = 0;
	int res = 0;

	for(int i = 30; i>=0; i--)
	{
		int t = x>>i&1;

		if(tr[p][!t]) 
		{
			p=tr[p][!t];
			res=2*res+1;
		}
		else
		{
			p=tr[p][t];
			res=2*res;
		}
	}

	return res;
}

void solve()
{
	int n;
	cin >> n;

	for(int i = 1; i<=n; i++)
	{
		cin >> a[i];
		insert(a[i]);
	}

	int ans = 0;
	for(int i = 1; i<=n; i++) ans=max(ans,que(a[i]));

	cout << ans <<endl;
}

signed main()
{
	solve();

	return 0;
}