9月2日的字符串

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 19930726;
const int maxn = 1e6 + 3;
char Ma[maxn<<1];
int Mp[maxn<<1];
ll cnt[maxn];
vector<ll> v;
void Manacher(char s[],int len)
{
	int l=0;
	Ma[l++]='$'; Ma[l++]='#';
	for(int i=0;i<len;i++) {
		Ma[l++]=s[i]; Ma[l++]='#';
	}
	int mx=0,id=0;
	for(int i=0;i<l;i++) {
		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
		if(i+Mp[i]>mx) id=i,mx=i+Mp[i];
	}
}
ll ksm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	int n;
	ll k,ans=1,now=0;
	char s[maxn];
	scanf("%d%lld%s",&n,&k,s);
	int len=strlen(s);
	Manacher(s,len);
	for(int i=2;i<2*len+2;i+=2) 
		cnt[Mp[i]-1]++;
	for(int i=n;i>=1;i--)
		if(i%2) {
			now+=cnt[i];
			if(k>=now) {
				ans=ans*ksm((ll)i,now)%mod; 
				k-=now; 
			}
			else {
				ans=ans*ksm((ll)i,k)%mod;
				k-=now;
				break;
			}
		}
	if(k>0) ans=-1;
	printf("%lld",ans);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
int Next[maxn],now,tot,f[maxn];
char ans[maxn];
void get_next(char x[],int len)
{
	Next[1]=0;
	for(int i=2,j=0;i<=len;i++) {
		while(j>0&&x[i]!=x[j+1]) j=Next[j];
		if(x[i]==x[j+1]) j++;
		Next[i]=j;
	}
}
int main()
{
	char s[maxn],t[maxn];
	scanf("%s%s",s+1,t+1);
	int n=strlen(s+1),m=strlen(t+1);
	get_next(t,m);
	for(int i=1,j=0;i<=n;i++) {
		ans[tot++]=s[i];
		while(j>0&&(j==n||ans[tot-1]!=t[j+1])) j=Next[j];
 		if(ans[tot-1]==t[j+1]) j++;
		f[tot-1]=j;	
		if(j==m) {
			tot-=m;
			j=f[tot-1];			
		}
	}
	for(int i=0;i<tot;i++) printf("%c",ans[i]);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 4;
struct Trie {
	int fail,ch[27],len;
}ac[maxn];
int tot,pos[maxn],top;
char ans[maxn];
void Insert(char s[])
{
	int len=strlen(s),now=0;
	for(int i=0;i<len;i++) {
		if(!ac[now].ch[s[i]-'a']) ac[now].ch[s[i]-'a']=++tot;
		now=ac[now].ch[s[i]-'a'];
	}
	ac[now].len=max(ac[now].len,len);
}
void build()
{
	ac[0].fail=0;
	queue<int> q;
	for(int i=0;i<26;i++) if(ac[0].ch[i]) 
	{
		ac[ac[0].ch[i]].fail=0; q.push(ac[0].ch[i]);
	}
	while(!q.empty())
	{
		int now=q.front(); q.pop();
		for(int i=0;i<26;i++) 
			if(ac[now].ch[i])
			{
				ac[ac[now].ch[i]].fail=ac[ac[now].fail].ch[i];
				q.push(ac[now].ch[i]);
			}
			else ac[now].ch[i]=ac[ac[now].fail].ch[i];
	}
}
void query(char s[])
{
	int now=0,len=strlen(s),tmp;
	for(int i=0;i<len;i++) {
		now=ac[now].ch[s[i]-'a'];
		ans[++top]=s[i];
		pos[top]=now;
		if(ac[now].len) {
			top-=ac[now].len;
			now=pos[top];
		}
	}
}
int main()
{
	char s[maxn],t[maxn];
	int n;
	scanf("%s%d",s,&n);
	for(int i=0;i<=maxn;i++) ac[i].len=0;
	for(int i=1;i<=n;i++) {
		scanf("%s",t);
		Insert(t);
	}
	build();
	query(s);
	for(int i=1;i<=top;i++) printf("%c",ans[i]);
	printf("\n");
	return 0;
}