Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍

【学习】字符串的各种

Jacinth posted @ 2016年8月08日 15:31 in Lerning with tags 字符串 学习 hash KMP 后缀自动机 Learning bzoj AC自动机 Manacher 回文自动机 , 980 阅读

感觉字符串很厉害啊。。。然而上次znz大神上课的时候并没有听懂就弃疗惹

感觉现在根本做不出字符串相关得怪窝？

蒟蒻还需努力哎╮(╯▽╰)╭

求不被怒D

然而这里是个坑

大家快去膜lbn！ 传送门： http://lbn187.is-programmer.com/posts/111869.html

nodes：原来的已经被修改丢掉辣TAT 所以时间点鬼畜的大家不要介意辣(╯‵□′)╯︵┻━┻

update 20160808: 感觉自己之前学的真是too young too simple啊

所以好好装修了一下QAQ

HASH&KMP

一直感觉kmp好难理解的，尤其是那个奇奇怪怪的next数组

但好像lbn上完课后感觉好多辣

又有一种。。。HASH好大啊的即视感

POI 2010 Beads

模拟串长直接暴力上啦

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

#define pb push_back
#define NN 1000005
typedef unsigned long long ULL;
const ULL B = 999983ull;
map <ULL,bool> mp;
vector <int> k;
int n,mx,a[NN];
ULL mul[NN],s1[NN],s2[NN];

ULL Ha(int l,int r)
{
	ULL tmp;
	if (l <= r)
		tmp = s1[r] - s1[l-1] * mul[r-l+1];
	else tmp = s2[r] - s2[l+1] * mul[l-r+1];
	return tmp;
}

void Solve(int xx)
{
	if (mx * xx > n) return;
	int ans = 0;
	mp.clear();
	for (int i=1;i<=n;i+=xx)
	if (i+xx-1 <= n)
	{
		ULL tmp = Ha(i,i+xx-1) * Ha(i+xx-1,i);
		if (mp[tmp]) continue;
		else ans ++, mp[tmp] = 1;
	}
	if (ans > mx) mx = ans, k.clear();
	if (ans == mx) k.pb(xx);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	mul[0] = 1;
	for (int i=1;i<=n;++i) mul[i] = mul[i-1] * B;
	for (int i=1;i<=n;++i) s1[i] = s1[i-1] * B + a[i];
	for (int i=n;i>=1;--i) s2[i] = s2[i+1] * B + a[i];
	for (int i=1;i<=n;++i) Solve(i);
	printf("%d %lu\n",mx,k.size());
	for (int i=0;i<k.size();++i)
	{
		printf("%d",k[i]);
		if (i<k.size()-1) printf(" ");
	}
	return 0;
}

POI2012 A Horrible Poem

1、循环节一定是长度的约数（好像是句废话TAT
2、如果n是一个循环节，那么k*n也必定是一个循环节
3、n是[l,r]这一段的循环节  的充要条件是  [l,r-n]和[l+n,r]相同（口胡
 
我们从性质2开始，如果len是循环节，那么最小循环节一定是len的约数
所以呢，我们要枚举所有的质因子，不断除以原长并保证其仍是循环节，直到不能再小为止。
然后就出解辣
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

#define NN 500005
#define N 500000
typedef unsigned long long ULL;
const ULL B = 999983ull;
ULL sum[NN],mul[NN];
char ch[NN];
int n,l,r,len,check[NN]={0},pri[NN]={0},m;

void Get_P()
{
	for (int i=2;i<=N;++i)
	{
		if (check[i] == 0) check[i] = i, pri[++pri[0]] = i;
		for (int j=1;j<=pri[0] && i*pri[j]<=N;++j)
		{
			check[i*pri[j]] = pri[j];
			if (i % pri[j] == 0) break;
		}
	}
}

bool Equal(int la,int ra,int lb,int rb)
{
	int tmp1 = sum[ra] - sum[la-1] * mul[ra-la+1];
	int tmp2 = sum[rb] - sum[lb-1] * mul[rb-lb+1];
	return (tmp1 == tmp2);
}

int main()
{
	Get_P();
	scanf("%d",&n);
	scanf("%s",ch+1);
	for (int i=1;i<=n;++i)
		sum[i] = sum[i-1] * B + ch[i];
	mul[0] = 1;
	for (int i=1;i<=n;++i) mul[i] = mul[i-1] * B;
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d%d",&l,&r);
		len = r-l+1;
		for (int i=len;i>1;)
		{
			int j = check[i];
			while (len%j==0 && Equal(l,r-len/j,l+len/j,r)) len/=j;
			while (i%j == 0) i/=j;
		}
		printf("%d\n",len);
	}
	return 0;
}

POI2006 Periods of Words

KMP好玩啊

next数组资磁哦

#include <bits/stdc++.h>

using namespace std;

#define NN 1001000
int n,k,ne[NN]={0};
long long ans=0ll;
char ch[NN];

int main()
{
	scanf("%d",&n);
	scanf("%s",ch+1);
	for (int i=2;i<=n;++i)
	{
		for (;k && ch[k+1] ^ ch[i];k = ne[k]);
		if (ch[k+1] == ch[i]) ++k;
		ne[i] = k;
	}
	for (int i=1;i<=n;++i)
	{
		while (ne[ne[i]]) ne[i] = ne[ne[i]];
	}
	for (int i=1;i<=n;++i)
	{
		if (ne[i] != 0) ans += i-ne[i];
	}
	printf("%lld\n",ans);
	return 0;
}

BZOJ3207 花神的嘲讽计划I

自爆辣

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

#define LL long long
#define NN 200005
#define MM 8000005
#define INF 18446744073709551615UL

int n,m,K,cnt = 0,val[NN],b[NN],rt[NN],sum[MM],a[MM][2];
unsigned LL H[NN],mod = 1UL;

void Ins(int xx,int &yy,unsigned LL val)
{
	yy = ++cnt;
	int tmp = yy;
	sum[yy] = sum[xx] + 1;
	unsigned LL l = 0, r = INF, mid;
	while (l!=r)
	{
		mid = l/2 + r/2;
		if ((l&1) && (r&1)) ++ mid;
		int t = 0;
		if (val > mid) t = 1,l = mid+1; else r = mid-1;
		a[yy][t] = ++cnt;
		a[yy][t^1] = a[xx][t^1];
		xx = a[xx][t] ,yy = a[yy][t], sum[yy] = sum[xx] +1;
	}
	yy = tmp;
}
bool Query(int xx,int yy,unsigned LL val)
{
	unsigned LL l = 0,r = INF,mid;
	while (l!=r)
	{
		mid = l/2 + r/2;
		if ((l&1) && (r&1)) ++mid;
		int t = 0;
		if (val > mid) t = 1, l = mid+1; else r = mid-1;
		xx = a[xx][t] ,yy = a[yy][t];
	}
	return (sum[yy] - sum[xx]) != 0;
}
int main()
{
	n = read(), m = read(), K = read();
	for (int i=1;i<=n;++i) val[i] = read();
	for (int i=1;i<=n;++i) H[i] = H[i-1] * 107+ val[i];
	for (int i=1;i<=K;++i) mod *= 107;
	for (int i=K;i<=n;++i) Ins(rt[i-1],rt[i],H[i]-H[i-K]*mod);
	int x,y;
	while (m--)
	{
		x = read(), y = read();
		for (int i=1;i<=K;++i) b[i] = read();
		unsigned LL now = 0;
		for (int i=1;i<=K;++i) now = now *107 + b[i];
		if (Query(rt[x+K-2],rt[y],now)) puts("No"); else puts("Yes");
	}
	return 0;
}

BZOJ-1009 [HNOI2008]GT考试

感觉是好久以前做的题了

当时的姿势水平只能看题解辣

好长的一段大家就去膜hzwer吧 http://hzwer.com/2955.html

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

string s;
int n,m,mod,ans;
int p[30],f[30][30],a[30][30],b[30][30];

void doing(int xx)
{
	if (xx>3) doing(xx/2);
	if (xx==1) return;
	memset(a,0,sizeof(a));
	for (int i=0;i<m;++i)
	for (int j=0;j<m;++j)
	for (int k=0;k<m;++k)
	a[i][j]=(a[i][j]+f[i][k]*f[k][j])%mod;
	memcpy(f,a,sizeof(a));
	if (xx%2==1)
	{
		memset(a,0,sizeof(a));
		for (int i=0;i<m;++i)
		for (int j=0;j<m;++j)
		for (int k=0;k<m;++k)
		a[i][j]=(a[i][j]+f[i][k]*b[k][j])%mod;
		memcpy(f,a,sizeof(f));
	}
	return;
}

int main()
{
	scanf("%d%d%d",&n,&m,&mod);
	memset(p,0,sizeof(p));
	memset(f,0,sizeof(f));
	memset(b,0,sizeof(b));
	cin>>s;
	s=" "+s;
	for (int i=2;i<s.length();i++)
	{
		int xx=p[i-1];
		while (s[i]!=s[xx+1]&&xx!=0) xx=p[xx];
		if (s[i]==s[xx+1]) p[i]=xx+1;
	}
	for (int i=0;i<s.length()-1;++i)
	{
		for (int j=0;j<=9;++j)
		{
			int xx=i;
			while (xx!=0&&j!=s[xx+1]-'0') xx=p[xx];
			if (j==s[xx+1]-'0') f[i][xx+1]++;
			else f[i][0]++;
		}
	}
	memcpy(b,f,sizeof(f));
	doing(n);
	ans=0;
	for(int i=0;i<m;++i) ans=(ans+f[0][i])%mod;
	printf("%d\n",ans%mod);
	return 0;
}

Manacher

马拉车这个鬼畜的名字是谁取的啊！(╯‵□′)╯︵┻━┻

BZOJ-2160 [2011集训队互测]拉拉队排练

先用Manacher求出数组后

用差分计算每一个长度的字符串出现的次数

暴力计算就好了～～

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

#define LL long long
#define mod 19930726ll
#define NN 2000500
char ch[NN];
LL ans,k,cnt=0ll,sum[NN]={0};
int mx,p,r[NN],n;
LL Pow(LL xx,LL yy) 
{
	LL sum=1ll;
	for (xx%=mod;yy;xx=xx*xx%mod,yy>>=1) if (yy&1) sum=sum*xx%mod;
	return sum;
}

int main()
{
	scanf("%d%lld",&n,&k);
	scanf("%s",ch+1);
	ch[0] = '#', ch[n+1] = '&';
	for (int i=1;i<=n;++i)
	{
		r[i] = (mx > i) ? min(r[2*p-i],mx-i) : 1;
		while (ch[i+r[i]] == ch[i-r[i]]) r[i] ++;
		if (r[i]+i > mx) mx = r[i] + i, p = i;
		sum[1] ++ , sum[r[i]+1] --;
	}
	for (int i=2;i<=n;++i) sum[i] += sum[i-1];
	ans = 1ll;
	for (int i=n;i>=1;--i)
		if (sum[i] + cnt <= k) ans = (ans * Pow(2*i-1,sum[i])) % mod, cnt += sum[i];
		else
		{
			ans = (ans * Pow(2*i-1,k-cnt)) % mod, cnt = k;
			break;
		}
	if (cnt < k) puts("-1"); else printf("%lld\n",ans);
	return 0;
}

BZOJ-2565 [2012清华集训]最长双回文串

先插入‘#’

那么就可以算出l[i]表示以i为结尾的最左的回文串的中心

然后枚举每一个‘#’当做断点，然后更新答案～～～

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

#define NN 200010
char c,ch[NN];
int r[NN],lm[NN],rm[NN],n=0,ans,mx,p;

void read()
{
	for (c = getchar();c<'a' || c>'z';c = getchar());
	ch[++n] = '#';
	ch[++n] = c;
	for (c = getchar();c>='a' && c<='z';ch[++n] = '#', ch[++n] = c, c = getchar());
	ch[++n] = '#';
}
int main()
{
	read();
	mx = 0;
	for (int i=1;i<=n;++i)
	{
		r[i] = (mx > i) ? min(r[2*p-i],mx-i+1) : 1;
		while (ch[i+r[i]] == ch[i-r[i]] && i-r[i] >= 1 && i+r[i] <= n) ++r[i];
		if (i+r[i]-1 > mx) mx = i+r[i]-1, p = i;
	}
	mx = r[0] = 0;
	for (int i=1;i<=n;++i)
	{
		if (i+r[i]-1 > mx)
		{
			for (int j=mx+1;j<=i+r[i]-1;++j) lm[j] = i;
			mx = i+r[i]-1;
		}
		if (mx == n) break;
	}
	mx = n+1;
	for (int i=n;i>=1;--i)
	{
		if (i-r[i]+1 < mx)
		{
			for (int j=i-r[i]+1;j<=mx-1;++j) rm[j] = i;
			mx = i-r[i]+1;
		}
		if (mx == 1) break;
	}
	for (int i=1;i<=n;++i)
		if (ch[i] == '#')
		{
			int tmp = (rm[i]-i+1 + i-lm[i]+1) * 2 - 3;
			if (tmp/2 > ans) ans = tmp/2;
		}
	printf("%d\n",ans);
	return 0;
}

AC自动机

BZOJ-3172 

Descriprtion 某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output 输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

Sample

Input

3

a

aa

aaa
Sample Output

6

3

1

AC自动机果题

#include <iostream> 
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#define NN 1000005
int n,pos[NN];
struct AC
{
	int cnt,ne[NN][26],sum[NN],fail[NN],que[NN];
	char ch[NN];
	acm()
	{	cnt=1; for (int i=0;i<26;++i) ne[0][i]=1;	}
	void Insert(int &pos)
	{
		int now=1;
		scanf("%s",ch);
		int len=strlen(ch);
		for (int i=0;i<len;++i)
		{
			if (!ne[now][ch[i]-'a']) ne[now][ch[i]-'a']=++cnt;
			now=ne[now][ch[i]-'a'];
			sum[now]++;
		}
		pos=now;
	}
	void buildfail()
	{
		int head=0, tail=1;
		que[0]=1, fail[1]=0;
		while (head!=tail)
		{
			int now=que[head]; head++;
			for (int i=0;i<26;++i)
			{
				int v=ne[now][i];
				if (!v) continue;
				int k=fail[now];
				while (!ne[k][i]) k=fail[k];
				fail[v]=ne[k][i];
				que[tail++]=v;
			}
		}
		for (int i=tail-1;i>=0;--i)
			sum[fail[que[i]]]+=sum[que[i]];
	}
}acm;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) acm.Insert(pos[i]);
	acm.buildfail();
	for (int i=1;i<=n;++i)
		printf("%d\n",acm.sum[pos[i]]);
	return 0;
}

BZOJ-2754

AC自动机模板+map、vector乱搞

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#define pb push_back
#define NN 100005
using namespace std;
int n,m,ans1[NN],ans2[NN];
bool vis[NN],mark[NN];
vector<int> a[20005],st[NN],V,M;
map<int,int> ne[NN];
struct T
{
	int cnt,fail[NN],que[NN];
	T()
	{
		cnt=1;
		for (int i=-1;i<=10000;++i) ne[0][i]=1;
		fail[1]=0;
	}
	void Insert(int pos)
	{
		int l,x,now=1;
		scanf("%d",&l);
		for (int i=1;i<=l;++i)
		{
			scanf("%d",&x);
			if (!ne[now][x]) ne[now][x]=++cnt;
			now=ne[now][x];
		}
		st[now].pb(pos);
	}
	void buildfail()
	{
		int head=0,tail=1; que[0]=1;
		while (head!=tail)
		{
			int now=que[head++];
			for (map<int,int>::iterator i=ne[now].begin();i!=ne[now].end();++i)
			{
				int t=i->first,k=fail[now];
				while (!ne[k][t]) k=fail[k];
				fail[i->second]=ne[k][t];
				que[tail++]=i->second;
			}
		}
	}
	void gets(int pos,int xx)
	{
		for (int i=xx;i;i=fail[i])
		if (!vis[i])
		{
			vis[i]=1, V.pb(i);
			for (int j=0;j<st[i].size();++j)
			if (!mark[st[i][j]])
			{
				mark[st[i][j]]=1, M.pb(st[i][j]);
				ans1[st[i][j]]++, ans2[pos]++;
			}
		}else break;
	}
	void solve(int xx)
	{
		int now=1;
		for (int i=0;i<a[xx].size();++i)
		{
			int t=a[xx][i];
			while (!ne[now][t]) now=fail[now];
			now=ne[now][t], gets(xx,now);
		}
		for (int i=0;i<V.size();++i) vis[V[i]]=0;
		for (int i=0;i<M.size();++i) mark[M[i]]=0;
		V.clear(); M.clear();
	}
}Trie;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
	{
		int l,x;
		scanf("%d",&l);
		while (l--) scanf("%d",&x), a[i].pb(x);
		a[i].pb(-1);
		scanf("%d",&l);
		while (l--) scanf("%d",&x), a[i].pb(x);
	}
	for (int i=1;i<=m;++i) Trie.Insert(i);
	Trie.buildfail();
	for (int i=1;i<=n;++i) Trie.solve(i);
	for (int i=1;i<=m;++i) printf("%d\n",ans1[i]);
	for (int i=1;i<n;++i) printf("%d ",ans2[i]); printf("%d\n",ans2[n]);
	return 0;
}

BZOJ-1030 JSOI2007 文本生成器

f[i][j]表示到第i个位置匹配自动机上第j个结点的方案数

感觉很多自动机上的DP都长这个样子

#include <bits/stdc++.h>
using namespace std;
const int mod = 10007;
const int NN = 6011;
int dp[101][NN],n,m,anss=1,ans=0;
char ch[110];

int cnt, ne[NN][26]={0},fail[NN],que[NN];
bool danger[NN];
void Clr() { cnt = 1; for (int i=0;i<26;++i) ne[0][i] = 1;}
void Insert()
{
	int now = 1,len = strlen(ch),c;
	for (int i=0;i<len;++i)
	{
		c=ch[i]-'A';
		if (!ne[now][c]) ne[now][c] = ++cnt;
		now = ne[now][c];
	}
	danger[now] = 1;
}
void Buildfail()
{
	int head = 0, tail = 1; que[0] = 1, fail[1] = 0;
	while (head != tail)
	{
		int now = que[head++];
		for (int i=0;i<26;++i)
		{
			int v = ne[now][i]; if (!v) continue;
			int k = fail[now]; while (!ne[k][i]) k = fail[k];
			fail[v] = ne[k][i], que[tail++] = v;
			if (danger[ne[k][i]]) danger[v] = 1;
		}
	}
}

void DP(int xx)
{
	for (int i=1;i<=cnt;++i)
	{
		if (danger[i] || !dp[xx-1][i]) continue;
		for (int j=0;j<26;++j)
		{
			int k = i;
			while (!ne[k][j]) k = fail[k];
			dp[xx][ne[k][j]] = (dp[xx][ne[k][j]] + dp[xx-1][i]) % mod;
		}
	}
}
int main()
{
	Clr();
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch);
		Insert();
	}
	Buildfail();
	dp[0][1] = 1;
	for (int i=1;i<=m;++i) DP(i);
	anss =1;
	for (int i=1;i<=m;++i) anss = (anss * 26) % mod;
	for (int i=1;i<=cnt;++i)
		if (!danger[i]) ans = (ans + dp[m][i]) % mod;
	printf("%d\n",(anss - ans + mod) % mod);	
	return 0;
}

BZOJ-1195 HNOI2006 最短母串

状压DP

其实类似于BFS辣

不过内存卡卡卡！！！

（lych：不卡内存的都不是正解

#include <bits/stdc++.h>
using namespace std;
const int NN = 601;
const int N = 1<<12;

char ch[110];
int cnt, ne[NN][26]={0},fail[NN],que[NN];
int dag[NN];

int la[NN*N],n,ans[NN],tot;
bool vis[NN][N];
short lac[NN*N],pre[NN*N],b[NN*N];

void Clr() { cnt = 1; for (int i=0;i<26;++i) ne[0][i] = 1;}
void Insert(int xx)
{
	int now = 1, len = strlen(ch), c;
	for (int i=0;i<len;++i)
	{
		if (!ne[now][c = ch[i]-'A']) ne[now][c] = ++cnt;
		now = ne[now][c];
	}
	dag[now] |= (1<<(xx-1));
}

void Buildfail()
{
	int head = 0, tail = 1; que[0] = 1, fail[1] = 0;
	while (head != tail)
	{
		int now = que[head++];
		for (int i=0;i<26;++i)
		{
			int v = ne[now][i];
			if (!v) 
			{
				ne[now][i] = ne[fail[now]][i];
				continue;
			}
			int k = fail[now]; while (!ne[k][i]) k = fail[k];
			fail[v] = ne[k][i], que[tail++] = v;
			dag[v] |= dag[fail[v]];
		}
	}
}
int main()
{
	scanf("%d",&n);
	Clr();
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch);
		Insert(i);
	}
	Buildfail();
	int head = 0, tail = 1;
	b[0] = pre[0] = 0;
	while (head != tail)
	{
		int u = b[head], now = pre[head];
		if (now == (1<<n)-1) break;
		for (int i=0;i<26;++i)
			if (!vis[ne[u][i]][now|dag[ne[u][i]]])
			{
				lac[tail] = i, la[tail] = head, b[tail] = ne[u][i], pre[tail] = now|dag[ne[u][i]];
				vis[ne[u][i]][pre[tail]] = 1;
				tail++;
			}
		head++;
	}
	for (;head;head=la[head]) ans[++tot] = lac[head];
	for (int i=tot-1;i>=1;--i) putchar('A'+ans[i]); puts("");
	return 0;
}

BZOJ-2746 SDOI2014 数数

直接在AC自动机上造树然后呢 LCA！

之前把LCA都快忘了TAT

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007LL
#define pb push_back
typedef long long LL;
const int NN = 1000100;

int n,m;
char ch[NN];
int cnt, ne[NN][26]={0},dep[NN],fa[NN][22];
vector <int> pos[NN];
LL ans[NN];
void Clr()
{
	cnt = 0; for (int i=0;i<26;++i) ne[0][i] = 0;
}
queue <int> que;
void Buildfail()
{
	for (int i=0;i<26;++i)
		if (ne[0][i])
		{
			que.push(ne[0][i]);
			fa[ne[0][i]][0] = 0;
			dep[ne[0][i]] = 1;
		}
	while (!que.empty())
	{
		int now = que.front(); que.pop();
		for (int i=0;i<26;++i)
		{
			int v = ne[now][i];
			if (!v)
			{
				ne[now][i] = ne[fa[now][0]][i]; continue;
			}
			int k = fa[now][0]; while (k && !ne[k][i]) k = fa[k][0];
			que.push(v);
			dep[v] = dep[ne[k][i]] + 1;
			fa[v][0] = ne[k][i];
		}
	}
}
void Buildlca()
{
	for (int j=1;j<20;++j)
		for (int i=1;i<=cnt;++i)
			fa[i][j] = fa[fa[i][j-1]][j-1];
}

int LCA(int xx,int yy)
{
	if (dep[xx] < dep[yy]) swap(xx,yy);
	int tmp = dep[xx] - dep[yy];
	for (int i=0;i<=20;++i)	 if (tmp>>i & 1) xx = fa[xx][i];
	for (int i=17;i>=0;--i) if (fa[xx][i] != fa[yy][i]) xx = fa[xx][i], yy = fa[yy][i];
	return (xx == yy) ? ans[xx]:ans[fa[xx][0]];
}
int main()
{
	Clr();
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch);
        int len = strlen(ch);  
        int x = 0;  
        for (int j = 0; j < len; j++) {  
            int po = ch[j] - 'a';  
            if (!ne[x][po]) {  
                ne[x][po] = ++cnt;  
                LL ADD = ch[j] - 'a';  
                ans[cnt] = (ans[x]*26LL + ADD)%mod;  
            }  
            x = ne[x][po];  
            pos[i].push_back(x);  
        }  
	}
	Buildfail();
	Buildlca();
	scanf("%d",&m);
	int xa,xb,ya,yb;
	while (m--)
	{
		scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
		printf("%d\n",LCA(pos[xa][ya-1],pos[xb][yb-1]));
	}
	return 0;
}

BZOJ-2434 NOI2011 阿狸的打字机

感觉会语死早
更资磁：http://hzwer.com/5423.html

#include <bits/stdc++.h>
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
const int NN = 100005;
int n,m,tot =0,T,l[NN],r[NN],tr[NN<<1],head[NN],laq[NN],pos[NN],ans[NN];

char ch[NN];
struct FT
{
	int v,ne;
}e[NN],q[NN];

int fail[NN],fa[NN],ne[NN][27],que[NN],cnt;

void Clr()
{
	cnt = 1;
	for (int i=0;i<26;++i) ne[0][i] = 1;
}

void Insert()
{
	int now = 1, id = 0,c;
	for (int i=0;i<n;++i)
		if (ch[i] == 'P') pos[++id] = now;
		else if (ch[i] == 'B') now = fa[now];
		else
		{
			if (!ne[now][c=ch[i]-'a'])
			{
				ne[now][c] = ++ cnt;
				fa[cnt] = now;
			}
			now = ne[now][c];
		}
}

void Buildfail()
{
	int head = 0, tail = 1; que[0] = 1, fail[1] = 0;
	while (head != tail)
	{
		int now = que[head++];
		for (int i=0;i<26;++i)
		{
			if (ne[now][i])
			{
				int v = ne[now][i];
				int k = fail[now];
				while (!ne[k][i]) k = fail[k];
				fail[v] = ne[k][i];
				que[tail++] = v;
			}
		}
	}
}

void Build(int xx,int yy)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
}

void DFS(int xx)
{
	l[xx] = ++T;
	for (int i=head[xx];i;i=e[i].ne) DFS(e[i].v);
	r[xx] = ++T;
}
int lowbit(int xx) { return xx & -xx;}
void Add(int xx,int yy)
{
	for (int i=xx;i<=T;i+=lowbit(i)) tr[i] += yy;
}
int query(int xx)
{
	int sum =0;
	for (int i=xx;i;i-=lowbit(i)) sum += tr[i]; return sum;
}
void Solve()
{
	int now = 1, id = 0;
	Add(l[1],1);
	for (int i=0;i<n;++i)
	{
		if (ch[i] == 'P')
		{
			++id;
			for (int x=laq[id];x;x=q[x].ne)
			{
				int tmp = pos[q[x].v];
				ans[x] = query(r[tmp]) - query(l[tmp]-1);
			}
		}
		else
		if (ch[i] == 'B') Add(l[now],-1), now = fa[now];
		else now = ne[now][ch[i]-'a'], Add(l[now],1);
	}	
}
int main()
{
	scanf("%s",ch);
	Clr();
	n = strlen(ch);
	Insert();
	Buildfail();
	for (int i=1;i<=cnt;++i) Build(fail[i],i);
	m = read();
	int x,y;
	for (int i=1;i<=m;++i)
	{
		x = read(), y = read();
		q[i].ne = laq[y];
		laq[y] = i;
		q[i].v = x;
	}
	DFS(0);
	Solve();
	for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

后缀自动机

BZOJ-3998 

Descriprtion 对于一个给定长度为N的字符串，求它的第K小子串是什么。
Input

第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
Output 输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1
Sample Input

aabc

0 3
Sample Output aab 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define NN 500050
#define MM 1000010
using namespace std;
int n,t,k;
char ch[NN];
struct SAM
{
	int tot,la,a[MM][30],mx[MM],fa[MM],v[NN],q[MM],val[MM],sum[MM];
	SAM(){ la=++tot;}
	void extend(int xx)
	{
		int p=la,np=la=++tot;
		mx[np]=mx[p]+1,val[np]=1;
		while (!a[p][xx] && p) a[p][xx]=np,p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			int q=a[p][xx];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				int nq=++tot; mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[q]));
				fa[nq]=fa[q],fa[np]=fa[q]=nq;
				while (a[p][xx]==q) a[p][xx]=nq,p=fa[p];
			}
		}
	}
	void pre()
	{
		for (int i=1;i<=tot;++i) v[mx[i]]++;
		for (int i=1;i<=n;++i) v[i]+=v[i-1];
		for (int i=tot;i;i--) q[v[mx[i]]--]=i;
		for (int i=tot;i;i--)
		{
			int tmp=q[i];
			if (t==1) val[fa[tmp]]+=val[tmp]; else val[tmp]=1;
		}
		val[1]=0;
		for (int i=tot;i;i--)
		{
			int tmp=q[i]; sum[tmp]=val[tmp];
			for (int j=0;j<26;++j) sum[tmp]+=sum[a[tmp][j]];
		}
	}
	void dfs(int xx,int yy)
	{
		if (yy<=val[xx]) return;
		yy-=val[xx];
		for (int i=0;i<26;++i)
			if (int tmp=a[xx][i])
			{
				if(yy<=sum[tmp])
				{
					putchar(i+'a'); dfs(tmp,yy); return;
				}
				yy-=sum[tmp];
			}
	}
}SAM;

int main()
{
	scanf("%s",ch+1); n=strlen(ch+1);
	scanf("%d%d",&t,&k);
	for (int i=1;i<=n;++i) SAM.extend(ch[i]-'a');
	SAM.pre();
	if (k>=SAM.sum[1]) { puts("-1"); return 0;}
	else SAM.dfs(1,k);
	return 0;
}

BZOJ-3926

神奇的题目描述啊。。。感觉语文不好的后果来了

ZJOI的题目呢。。。马上省选了好虚。。强省蒟蒻滚粗无疑辣。。

#include <iostream> 
#include <cstdio> 
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#define LL long long
#define MM 4000005
#define NN 100005
using namespace std;
LL ans;
int n,c,cc[NN],d[NN],tot=0,head[NN];
struct Edge
{
	int ne,v;
}e[NN<<1];
void Build(int xx,int yy)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy;
	e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx;
}
struct SAM
{
	int cnt,fa[MM],a[MM][10],mx[MM];
	SAM(){cnt=1;}
	int extend(int p,int c)
	{
		int np=++cnt; mx[np]=mx[p]+1;
		while (!a[p][c] && p) a[p][c]=np, p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			int q=a[p][c];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				int nq=++cnt;mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[q]));
				fa[nq]=fa[q], fa[np]=fa[q]=nq;
				while (a[p][c]==q) a[p][c]=nq, p=fa[p];
			}
		}
		return np;
	}
	void solve()
	{
		for (int i=1;i<=cnt;++i) ans+=mx[i]-mx[fa[i]];
	}
}Sam;
void DFS(int x,int fa,int p)
{
	int t=Sam.extend(p,cc[x]);
	for (int i=head[x];i;i=e[i].ne)
		if (e[i].v!=fa)
			DFS(e[i].v,x,t);
}
int main()
{
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;++i) scanf("%d",&cc[i]);
	int x,y;
	for (int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		Build(x,y);
		d[x]++, d[y]++;
	}
	for (int i=1;i<=n;++i)
		if (d[i]==1) DFS(i,0,1);
	Sam.solve();
	printf("%lld\n",ans);
	return 0;
}

BZOJ-4199

唔。。2015年的NOI题目呢。。。别忘了考虑负数。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define NN 600006
#define INF 2e18
using namespace std;
LL mav[NN],ma1[NN],ma2[NN],mi1[NN],mi2[NN],head[NN],n,m,a[NN],size[NN],ans[NN],tot=0;
bool vis[NN];
char ch[NN];
struct Edge
{
	int v,ne,w;
}e[NN];
void Build(LL xx,LL yy,LL zz)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
}
struct SAM
{
	LL cnt,la,ne[NN][26],fa[NN],mx[NN],t[NN],now,tmp,nx[NN];
	SAM(){la=++cnt;}
	void extend(int xx)
	{
		LL p=la,np=la=++cnt,c=ch[xx]-'a'; 
		mx[np]=mx[p]+1, t[np]=xx;
		while (!ne[p][c] && p) ne[p][c]=np, p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			LL q=ne[p][c];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				LL nq=++cnt; mx[nq]=mx[p]+1;
				memcpy(ne[nq],ne[q],sizeof(ne[q]));
				fa[nq]=fa[q], fa[np]=fa[q]=nq;
				while (ne[p][c]==q) ne[p][c]=nq, p=fa[p];
			}
		}
	}
	void DFS(LL xx,LL h)
	{
		if (t[xx]) ma1[xx]=mi1[xx]=a[t[xx]], size[xx]=1;
			else ma1[xx]=-INF,mi1[xx]=INF, size[xx]=0;
		ma2[xx]=-INF, mi2[xx]=INF;
		for (LL i=head[xx];i;i=e[i].ne)
		{
			LL yy=e[i].v;
			DFS(yy,h+e[i].w);
			if (ma1[yy]>ma1[xx])
			{
				ma2[xx]=ma1[xx], ma1[xx]=ma1[yy];
				if (ma2[yy]>ma2[xx]) ma2[xx]=ma2[yy];
			}
			else
			if (ma1[yy]>ma2[xx]) ma2[xx]=ma1[yy];
			if (mi1[yy]<mi1[xx])
			{
				mi2[xx]=mi1[xx], mi1[xx]=mi1[yy];
				if (mi2[yy]<mi2[xx]) mi2[xx]=mi2[yy];
			}
			else
			if (mi1[yy]<mi2[xx]) mi2[xx]=mi1[yy];
			size[xx]+=size[yy], nx[xx]+=nx[yy];
		}
		now=-INF; tmp=(size[xx]*(size[xx]-1))/2;
		if (size[xx]>=4)now=max(max(ma1[xx]*ma2[xx],mi1[xx]*mi2[xx]),max(ma1[xx]*mi2[xx],ma2[xx]*mi1[xx]));
		else
		if (size[xx]>=3) now=max(max(ma1[xx]*ma2[xx],mi1[xx]*mi2[xx]),ma1[xx]*mi1[xx]);
		else
		if (size[xx]>=2) now=ma1[xx]*ma2[xx];
		if (now!=INF) ans[h]+=tmp-nx[xx], mav[h]=max(mav[h],now);
		nx[xx]+=tmp-nx[xx];
	}
}Sam;
int main()
{
	scanf("%lld",&n);
	scanf("%s",ch+1);
	for (LL i=n;i;i--) Sam.extend(i);
	vis[1]=1;
	for (LL i=1;i<=Sam.cnt;++i)
		if (Sam.t[i]&&!vis[i])
			for (LL j=i;!vis[j];vis[j]=1,j=Sam.fa[j]) Build(Sam.fa[j],j,Sam.mx[j]-Sam.mx[Sam.fa[j]]);
	for (LL i=0;i<=n;++i) mav[i]=-INF;
	for (LL i=1;i<=n;++i) scanf("%lld",&a[i]);
	Sam.DFS(1,0);
	for (LL i=n-1;i>=0;--i) ans[i]=ans[i]+ans[i+1], mav[i]=max(mav[i],mav[i+1]);
	for (LL i=0;i<n;++i)
	{
		if (mav[i]==-INF) mav[i]=0;
		printf("%lld %lld\n",ans[i],mav[i]);
	}
	return 0;
}

后缀数组 SA

听说并没有什么卵用

听说可以被后缀自动机完美取代

反正板子太长了也不怎么想背

理解起来好像一样难qaq

BZOJ-1031

SA的题目，恶补字符串辣

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define NN 200010
using namespace std;
int sa[2][NN],rank[2][NN],v[NN],a[NN],len,k;
char ch[NN];

void Calsa(int sa[NN],int rank[NN],int SA[NN],int Rank[NN])
{
	for (int i=1;i<=len;++i) v[rank[sa[i]]]=i;
	for (int i=len;i>=1;--i)
		if (sa[i]>k)
			SA[v[rank[sa[i]-k]]--]=sa[i]-k;
	for (int i=len-k+1;i<=len;++i) SA[v[rank[i]]--]=i;
	for (int i=1;i<=len;++i)
		Rank[SA[i]]=Rank[SA[i-1]]+(rank[SA[i-1]]!=rank[SA[i]] || rank[SA[i-1]+k]!=rank[SA[i]+k]);
}
void Work()
{
	int p=0,q=1;
	for (int i=1;i<=len;++i) v[a[i]]++;
	for (int i=1;i<=256;++i) v[i]+=v[i-1];
	for (int i=1;i<=len;++i) sa[p][v[a[i]]--]=i;
	for (int i=1;i<=len;++i) rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
	k=1;
	for (k=1;k<len;p^=1,q^=1,k<<=1) Calsa(sa[p],rank[p],sa[q],rank[q]);
	for (int i=1;i<=len;++i)
		if (sa[p][i]<=len/2) printf("%c",ch[sa[p][i]+len/2-1]);
	puts("");
}
int main()
{
	scanf("%s",ch+1);
	len=strlen(ch+1);
	for (int i=1;i<=len;++i)
		a[i]=int(ch[i]), a[i+len]=a[i], ch[i+len]=ch[i];
	len<<=1;
	Work();
	return 0;
}C

BZOJ-3238

感觉后缀数组并不是正解。。时间好长（zhǎng）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define NN 500005
#define INF 0x3f3f3f3f
#define LL long long
int v[NN],a[NN],rank[2][NN],sa[2][NN],st[NN],l[NN],r[NN],len,top,h[NN],k;
LL ans;
char ch[NN];
void Calsa(int sa[NN],int rank[NN],int SA[NN],int Rank[NN])
{
	for (int i=1;i<=len;++i) v[rank[sa[i]]]=i;
	for (int i=len;i>=1;--i)
		if (sa[i]>k) SA[v[rank[sa[i]-k]]--]=sa[i]-k;
	for (int i=len-k+1;i<=len;++i) SA[v[rank[i]]--]=i;
	for (int i=1;i<=len;++i)
		Rank[SA[i]]=Rank[SA[i-1]]+(rank[SA[i-1]]!=rank[SA[i]] || rank[SA[i-1]+k]!=rank[SA[i]+k]);
}
void PreSA()
{
	int p=1,q=0;
	for (int i=1;i<=len;++i) v[a[i]]++;
	for (int i=1;i<=30;++i) v[i]+=v[i-1];
	for (int i=1;i<=len;++i) sa[p][v[a[i]]--]=i;
	for (int i=1;i<=len;++i) rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
	for (k=1;k<len;k<<=1,p^=1,q^=1)	Calsa(sa[p],rank[p],sa[q],rank[q]);
	for (int k=0,i=1;i<=len;++i)
	{
		int j=sa[p][rank[p][i]-1];
		while (a[j+k]==a[i+k]) ++k;
		h[rank[p][i]]=k; if (k>0) k--;
	}
}
void Solve()
{
	for (int i=1;i<=len;++i) ans+=(LL)i*(len-1);
	h[0]=-INF;
	for (int i=1;i<=len;++i)
	{
		while (h[i]<=h[st[top]]) top--;
		if (st[top]==0) l[i]=1; else l[i]=st[top]+1;
		st[++top]=i;
	}
	h[len+1]=-INF, top=0, st[0]=len+1;
	for (int i=len;i;i--)
	{
		while (h[i]<h[st[top]]) top--;
		if (st[top]==len+1) r[i]=len; else r[i]=st[top]-1;
		st[++top]=i;
	}
	for (int i=1;i<=len;++i) ans-=2ll*(i-l[i]+1)*(r[i]-i+1)*h[i];
}
int main()
{
	scanf("%s",ch+1);
	len=strlen(ch+1);
	for (int i=1;i<=len;++i) a[i]=ch[i]-'a'+1;
	PreSA();
	Solve();
	printf("%lld\n",ans);
	return 0;
}

 回文自动机

BZOJ-3676

听说这题自从有了回文自动机这种东西以后就成为了裸题QAQ

反正就是冲着这个板子来的（感谢黄学长的板子啦啦啦

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

#define LL long long
#define NN 300005
int n;
char ch[NN];
LL ans = 0ll;

struct Pam
{
	int cnt,la,fa[NN],l[NN],size[NN],a[NN][30];
	
	Pam() {	cnt = 1, fa[0] = fa[1] = 1, l[1] = -1;}
	void extend(int c,int n)
	{
		int p = la;
		while (ch[n-l[p]-1] != ch[n]) p = fa[p];
		if (!a[p][c])
		{
			int now = ++cnt, k = fa[p];
			l[now] = l[p] + 2;
			while (ch[n-l[k]-1]!=ch[n]) k = fa[k];
			fa[now] = a[k][c];
			a[p][c] = now;
		}
		la = a[p][c];
		size[la] ++ ;
	}
	void solve()
	{
		for (int i=cnt;i;i--)
		{
			size[fa[i]] += size[i];
			ans = max(ans,(LL)size[i] * l[i]);
		}
	}
}Pam;
int main()
{
	scanf("%s",ch+1);
	n = strlen(ch+1);
	for (int i=1;i<=n;++i) Pam.extend(ch[i]-'a',i);
	Pam.solve();
	printf("%lld\n",ans);
	return 0;
}
Small_feed 评论 (1)
1
[回复]
Avatar_small
MBOSE Question Paper 说:
2022年8月25日 20:03

Meghalaya Board Model Paper 2023 Class 11 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay MBOSE Question Paper Class 11 Type Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter