acdream1116 Gao the string!(扩展KMP)

今天是字符串填坑的一天,首先填的第一个坑是扩展KMP。总结一下KMP和扩展KMP的区别。

在这里s是主串，t是模式串。

KMP可以求出的是以s[i]为结尾的串和 t前缀匹配的最长的长度。假如这个长度是L的话，则：

s[i-L+1...i]=t[0...L]

而所谓的失配指针f[i]指的就是当前i点失配时要匹配的长度，实际是用t文本串去匹配t。

扩展KMP则是以s[i]为起始的串和 t前缀匹配的最长的长度。假如这个长度的话，则：

s[i..i+L-1]=t[0...L]

扩展KMP里的nxt数组就是利用t本身和自己匹配达到的效果。所以nxt[i]就是以t的后缀i和t的前缀匹配的最长的长度，有了这个就可以用来求上次的这道题了。

自己写的时候写了个后缀数组的版本，可以将t的前缀理解成后缀0，于是就是后缀之间的最长前缀，就是利用lcp来求，无奈的是后缀数组本身求的速度太慢了，rmq的速度更慢。由于扩展KMP是线性的，所以这次就可以顺利的过了这道坑爹题了。

下面第一个网里有一些理论的证明，但KMP那部分和我学的不太一样，不知道是我搞错了还是版本不一样，然后第二个链接里的代码感觉写的可读性强一点，在这里存一下模板。

http://www.cnblogs.com/10jschen/archive/2012/09/03/2668149.html

http://www.cnblogs.com/kuangbin/archive/2012/08/27/2659246.html

#pragma warning(disable:4996)

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

#define ll long long

#define mxs 1000000

#define mxt 100000

#define mod 1000000007

char s[mxs], t[mxt];

int nxt[mxt], ex[mxt];

// get the next array for t only

void getNext(char *t,int *nxt)

{

	int m = strlen(t);

	nxt[0] = m;

	int j = 0;

	while (j + 1 < m&&t[j] == t[j + 1]) j++;

	nxt[1] = j;

	int k = 1; int p, L;

	for (int i = 2; i < m; i++)

	{

		p = nxt[k] + k - 1;

		L = nxt[i - k];

		if (i + L < p + 1) nxt[i] = L; // i+L<=p

		else

		{

			j = max(0, p - i + 1);

			while (i + j < m&&t[i + j] == t[0 + j])j++;

			nxt[i] = j;

			k = i;

		}

	}

}

// get the next array for t, and get the ex array for s;

void getExtend(char *s, char *t, int *nxt, int *ex)

{

	getNext(t, nxt);

	int n = strlen(s), m = strlen(t);

	int j = 0;

	while (j < n&&j < m&&s[j] == t[j]) j++;

	ex[0] = j;

	int k = 0; int p, L;

	for (int i = 1; i < n; i++){

		p = ex[k] + k - 1;

		L = nxt[i - k];

		if (i + L < p + 1) ex[i] = L;

		else{

			j = max(0, p - i + 1);

			while (i + j < n&&j < m&&s[i + j] == t[j]) j++;

			ex[i] = j;

			k = i;

		}

	}

}

struct Matrix

{

	ll a[2][2];

	Matrix(){ memset(a, 0, sizeof(a)); }

}m;

Matrix operator * (const Matrix &a, const Matrix &b){

	Matrix ret;

	for (int i = 0; i < 2; i++){

		for (int j = 0; j < 2; j++){

			for (int k = 0; k < 2; k++){

				ret.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;

				ret.a[i][j] %= mod;

			}

		}

	}

	return ret;

}

Matrix operator ^ (Matrix a, ll n){

	Matrix ret;

	for (int i = 0; i < 2; i++) ret.a[i][i] = 1;

	while (n){

		if (n & 1) ret = ret*a;

		n >>= 1;

		a = a*a;

	}

	return ret;

}

ll cal(ll n)

{

	m.a[0][0] = 0; m.a[0][1] = 1;

	m.a[1][0] = 1; m.a[1][1] = 1;

	m = m^n;

	return m.a[0][1];

}

int main()

{

	while (~scanf("%s",s)){

		getNext(s, nxt);

		int n = strlen(s);

		nxt[n] = 0;

		ll ans = 0;

		for (int i = n - 1; i >= 0; i--){

			nxt[i] += nxt[i + 1];

			ans += cal(nxt[i]);

			ans %= mod;

		}

		printf("%lld\n", ans);

	}

	return 0;

}

巴特西

acdream1116 Gao the string!(扩展KMP)

最新文章

热门文章