小Y的字符串——扩展KMP

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目链接

题目描述

总所周知的是，小Y对于字符串之类的题目总是很得心应手的，这一天漂亮的学妹问了小Y一个题目，问两个字符串怎样进行字典序大小比较，当然啦，这种题目对于小Y来说简直是太太太太太简单的啦~~~~于是小Y只花了一点时间就和学妹说清楚了。

不过为了和学妹获得更多的相处时间，小Y灵机一动，给学妹提了一道看似简单的问题，问给定一两个字符串a，b，问a里面有多少个子串字典序小于b。

学妹算着算着就迷糊了，于是她向你求助，如果你帮助她解决这个问题，那么可能漂亮的学妹会考虑一下让你做她男朋友哦~~~(题目保证输入全部为小写英文字母)

输入描述:

输入两个字符串a,b(1<=|b|<|a|<=200000)。

输出描述:

输出一个数,表示a的子串里面有多少个串字典序小于b串。

示例1

输入

aababac ba

输出

示例2

输入

bcefeghijklmn df

输出

题解：扩展KMP的应用。可以把题意转化为a的所有后缀与b的最长匹配（扩展KMP求解），然后比较字典序求和。一位大佬的代码，orz！

扩展KMP：定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。

AC代码：

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

const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 10;
char s[MAXN], p[MAXN]; //主串 模式串
int n, m; //s长度 p长度
int exnex[MAXN], exten[MAXN]; //扩展next数组 s从i为起点的后缀与p的最长公共前缀

void getexnext()
{
	int i = 0, j;
	exnex[0] = m; //0号位为长度
	while (i + 1 < m && p[i] == p[i + 1]) //计算第一项
		i++;
	exnex[1] = i;
	int k = 1 + i, po = 1; //k最远到达点 po最远到达点的起点
	for (i = 2; i < m; i++)
	{
		if (exnex[i - po] < k - i) //因k~po == 0~k-po 则i~k == i-po~k-po(取前者后一部分)
			exnex[i] = exnex[i - po]; //如果exnet[i-po]不足k-i长度则s[i - po + exnet[i-po]] != s[i + exnet[i-po]]
		else
		{
			j = k - i;//如果长度相等或更长因k之后为未探索区域 暂定为k - i之后继续匹配
			if (j < 0) //如果i本身就超过k
				j = 0;
			while (i + j < m && p[i + j] == p[j])
				j++;
			exnex[i] = j;
			k = i + j, po = i; //更新记录
		}
	}
}
void exkmp()
{
	getexnext(); //计算exnext
	int i = 0, j;
	while (s[i] == p[i] && i < m && i < n) //计算第零项
		i++;
	exten[0] = i;
	int k = i, po = 0; 
	for (i = 1; i < n; i++) //从1开始计算
	{
		if (exnex[i - po] < k - i)
			exten[i] = exnex[i - po]; //exten
		else
		{
			j = k - i;
			if (j < 0)
			j = 0;
			while (i + j < n && j < m && s[i + j] == p[j]) //n m s
				j++;
			exten[i] = j; //exten
			k = i + j, po = i;
		}
	}
}
int main()
{
	cin >> s >> p;
	n = strlen(s); //按需求添加
	m = strlen(p);
	exkmp();
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += min(exten[i], m - 1); //相同部分的每一个前缀都是 不能和b相等
		if (s[i + exten[i]] < p[exten[i]]) //不同部分比较字典序 如果小则有n - i - exten[i]个
			ans += n - i - exten[i];
	}
	cout << ans << endl;
	return 0;
}

扩展KMP模板：

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

const int INF = 0x3f3f3f3f;
const int MAXN = 1e3 + 10;
char s[MAXN], p[MAXN]; //主串 模式串
int n, m; //s长度 p长度
int exnex[MAXN], exten[MAXN]; //扩展next数组 s从i为起点的后缀与p的最长公共前缀

void getexnext()
{
	int i = 0, j;
	exnex[0] = m; //0号位为长度
	while (i + 1 < m && p[i] == p[i + 1]) //计算第一项
		i++;
	exnex[1] = i;
	int k = 1 + i, po = 1; //k最远到达点 po最远到达点的起点
	for (i = 2; i < m; i++)
	{
		if (exnex[i - po] < k - i) //因k~po == 0~k-po 则i~k == i-po~k-po(取前者后一部分)
			exnex[i] = exnex[i - po]; //如果exnet[i-po]不足k-i长度则s[i - po + exnet[i-po]] != s[i + exnet[i-po]]
		else
		{
			j = k - i;//如果长度相等或更长因k之后为未探索区域 暂定为k - i之后继续匹配
			if (j < 0) //如果i本身就超过k
				j = 0;
			while (i + j < m && p[i + j] == p[j])
				j++;
			exnex[i] = j;
			k = i + j, po = i; //更新记录
		}
	}
}
void exkmp()
{
	getexnext(); //计算exnext
	int i = 0, j;
	while (s[i] == p[i] && i < m && i < n) //计算第零项
		i++;
	exten[0] = i;
	int k = i, po = 0; 
	for (i = 1; i < n; i++) //从1开始计算
	{
		if (exnex[i - po] < k - i)
			exten[i] = exnex[i - po]; //exten
		else
		{
			j = k - i;
			if (j < 0)
				j = 0;
			while (i + j < n && j < m && s[i + j] == p[j]) //n m s
				j++;
			exten[i] = j; //exten
			k = i + j, po = i;
		}
	}
}
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	cin >> s >> p;
	n = strlen(s); //按需求添加
	m = strlen(p);

	return 0;
}
/*
aaaabaaaaa
*/

秒客网

小Y的字符串——扩展KMP

相关文章