【HDU 5716】带可选字符的多字符串匹配

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html

解题报告

这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$

Code

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

const int N = 2000009;
const int M = 600;
const int SGZ = 100;

char s[N], sgz[SGZ];
bitset<M> v, f[SGZ];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int id(char c) {
	if ('0' <= c && c <= '9') {
		return c - '0' + 1;
	} else if ('a' <= c && c <= 'z') {
		return c - 'a' + 11;
	} else if ('A' <= c && c <= 'Z'){
		return c - 'A' + 37;
	} else {
		return 0;
	}
}

int main() {
	while (gets(s + 1)) {
		int n = strlen(s + 1), m = read();
		v.reset();
		for (int i = 0; i < SGZ; i++) {
			f[i].reset();
		}
		for (int i = 1; i <= m; i++) {
			int SGZ = read();
			scanf("%s", sgz + 1);
			for (int j = 1; j <= SGZ; j++) {
				f[id(sgz[j])][i] = 1;
			}
		}
		bool CantMatch = 1;
		for (int i = 1; i <= n; i++) {
			v = (v << 1) & f[id(s[i])];
			v[1] = f[id(s[i])][1];
			if (v[m]) {
				printf("%d\n", i - m + 1);
				CantMatch = 0;
			}
		}
		if (CantMatch) {
			puts("NULL");
		}
		getchar();
	}
	return 0;
}

—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924

【BZOJ 4231】回忆树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4231
数据生成器:http://paste.ubuntu.com/24366714/
神犇题解:http://www.cnblogs.com/clrs97/p/5467637.html

解题报告

首先我们如果最终一个串出现的位置会越过$LCA$
那么我们可以把这一部分的情况单独拿出来,暴力跑$KMP$

剩下就是单纯地从根节点向下,或者向上的路径中出现了多少次
这不难让我们想到广义后缀自动机,但似乎这题并不能用

考虑另一个方法,把所有模式串建成AC自动机
然后在原树上$DFS$,进入一个点时将其在AC自动机对应的结点权值$+1$
退出来的时候将其$-1$,那么我们在需要询问的时候统计一下子树的权值和就可以了

总时间复杂度:$O(n \log n + \sum |S|)$

Code

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

const int N = 100009;
const int M = 600009;

int n,m,head[N],nxt[M],to[M],cost[M],U[N];
int pp[N][2],ans[N],dep[N],fa[N][20],C[N];
vector<pair<int,int> > qry[N]; 

class AC_Automaton{
	int dfs_cnt,ch[M][26],fail[M],in[M],out[M];
	queue<int> que; vector<int> sn[M]; 
	struct Fenwick_Tree{
		int sum[M],sz;
		inline int lowbit(int x) {return x & -x;}
		inline void modify(int w, int delta) {
			for (int i=w;i<=sz;i+=lowbit(i)) sum[i] += delta;
		}
		inline int query(int l, int r) {
			int ret = 0; l--;
			for (int i=l;i;i-=lowbit(i)) ret -= sum[i];
			for (int i=r;i;i-=lowbit(i)) ret += sum[i];
			return ret;
		}
	}BIT;
	public:
		inline void build() {
			for (int i=0;i<26;i++) ch[0][i]=1;
			que.push(1); fail[1] = 0;
			while (!que.empty()) {
				int w = que.front(); que.pop();
				sn[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i]) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else ch[w][i] = ch[fail[w]][i];
				}
			}
			DFS(1);
			BIT.sz = dfs_cnt;
		}
		inline int insert(char *s) {
			static int cnt = 1;
			int w = 1, len = strlen(s+1);
			for (int i=1,c;i<=len;i++) {
				if (!ch[w]-'a']) ch[w] = ++cnt;
				w = ch[w]; 
			} 
			return w;
		}
		inline int query(int p) {
			return BIT.query(in[p], out[p]);
		}
		inline void modify(int p, int delta) {
			BIT.modify(in[p], delta);
		}
		inline int move(int w, int c) {
			return ch[w];
		}
	private:
		void DFS(int w) {
			in[w] = ++dfs_cnt;
			for (int i=sn[w].size()-1;~i;i--)
				if (!in[sn[w][i]]) DFS(sn[w][i]);
			out[w] = dfs_cnt;
		}
}ac;

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

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int j=19;~j;j--) if (dep[fa[a][j]] >= dep[b]) a = fa[a][j];
	if (a == b) return a;
	for (int j=19;~j;j--) if (fa[a][j] != fa[b][j]) a = fa[a][j], b = fa[b][j];
	return fa[a][0];
}

void pre(int w, int f) { 
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) 
		C[to[i]] = cost[i], pre(to[i], w);
}

void solve(int w, int p) { 
	for (int i=qry[w].size()-1,f;~i;i--) {
		if (qry[w][i].first>0) f = 1; else f = -1, qry[w][i].first *= -1;
		ans[qry[w][i].first] += ac.query(pp[qry[w][i].first][qry[w][i].second]) * f;
	}
	for (int i=head[w],tmp;i;i=nxt[i]) {
		if (dep[to[i]] > dep[w]) {
			tmp = ac.move(p, cost[i]); 
			ac.modify(tmp, 1); 
			solve(to[i], tmp);
			ac.modify(tmp, -1); 
		}
	}
}

inline int dif(int &u, int &v, int lca, char *s, int len) {
	static char ss[M]; static int NXT[M]; int tot = 0, TOT;
	int w = u, l = dep[u] - dep[lca] - len + 1, ret = 0;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; u = w;} 
	while (w != lca) ss[++tot] = C[w] + 'a', w = fa[w][0];
	w = v; l = dep[v] - dep[lca] - len + 1;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; v = w;}
	TOT = (tot += dep[w] - dep[lca]);
	while (w != lca) ss[tot--] = C[w] + 'a', w = fa[w][0];
	
	for (int i=1,w;i<=len;i++) {
		for (w=NXT[i];w&&s[w+1]!=s[i+1];w=NXT[w]);
		NXT[i+1] = w + (s[w+1] == s[i+1]);
	}
	for (int i=1,w=0;i<=TOT;i++) {
		for (;w&&s[w+1]!=ss[i];w=NXT[w]);
		w += s[w+1] == ss[i];
		ret += w == len;
	} 
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		char c[2]; scanf("%s",c);
		AddEdge(u, v, c[0] - 'a');
	} 
	pre(1, 1); 
	for (int j=1;j<=19;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	char pat[300009];
	for (int i=1,u,v,lca,ll,p1,p2;i<=m;i++) {
		U[i] = u = read(); v = read(); lca = LCA(u, v);
		scanf("%s",pat+1); pp[i][0] = ac.insert(pat); ll = strlen(pat+1);
		qry[u].push_back(make_pair(i,1)); qry[v].push_back(make_pair(i,0)); 
		ans[i] += dif(u, v, lca, pat, ll); 
		qry[u].push_back(make_pair(-i,1)); qry[v].push_back(make_pair(-i,0));
		for (int l=1,r=ll;l<r;l++,r--) swap(pat[l], pat[r]); pp[i][1] = ac.insert(pat);
	} 
	ac.build();
	solve(1, 1);
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

【日常小测】图片加密

题目大意

给定两个数字串$A,B$,长度分别为$n,m(m \le n \le 250000)$
串中的元素为$<512$的自然数,你可以花费一个单位的代价改变一个元素在二进制下的最低位
询问能否通过修改操作使得$B$在$A$中出现
如果可以,请输出最小的花费和在花费最小的前提下最左边的匹配位置

解题报告

我们发现高位不可改,于是我们用$KMP$统计一下高位的合法位置
至于低位,我们可以拆成两次$FFT$
于是搞一搞就可以了

至于为什么我写的是$SA$?
因为考场上忘掉$KMP$怎么写了 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 550000;
const int M = N << 1;
const int INF = 1e9;
const int MOD = 1004535809;
 
int n,m,L,a1[M],a2[N],o1[N],o2[N],leg[N],ans[N]; 
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline int Read() {
    static char pat[20]; scanf("%s",pat+1); int ret = 0;
    for (int i=8,w=1;i;i--,w<<=1) ret += (pat[i]-'0') * w; 
    return ret;
}
 
 
class Suffix_Array{
    int len,tot,*rak,*que,bot[N],sa[M],arr1[M],arr2[M],height[N];
    public:
        inline void build() {
            rak = arr1; que = arr2; len = n + m + 1;
            a1[0] = -1; a1[len+1] = -2;
            for (int i=1;i<=len;i++) ++bot[a1[i]];
            for (int i=1;i<=100000;i++) bot[i] += bot[i-1];
            for (int i=1;i<=len;i++) sa[bot[a1[i]]--] = i;
            rak[sa[1]] = tot = 1;
            for (int i=2;i<=len;i++) rak[sa[i]] = (a1[sa[i]]==a1[sa[i-1]])? tot: ++tot;
            for (int l=1,cnt;cnt=0,l<=len;l<<=1) {
                for (int i=len-l+1;i<=len;i++) que[++cnt] = i;
                for (int i=1;i<=len;i++) if (sa[i]>l) que[++cnt] = sa[i] - l;
                for (int i=0;i<=tot;i++) bot[i] = 0;
                for (int i=1;i<=len;i++) bot[rak[i]]++;
                for (int i=1;i<=tot;i++) bot[i] += bot[i-1];
                for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i];
                swap(que, rak); rak[sa[1]] = tot = 1;
                for (int i=2;i<=len;i++) 
                    if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]] = tot;
                    else rak[sa[i]] = ++tot;
                if (tot >= len) break;
            }
            GetHeight();
        }
        inline void solve() {
            for (int i=rak[n+2];height[i]>=m;i--) if (sa[i] <= n) leg[sa[i]] = 1;
            for (int i=rak[n+2]+1;height[i]>=m;i++) if (sa[i] <= n) leg[sa[i]] = 1;
        }
    private:
        inline void GetHeight() {
            for (int i=1;i<=len;i++) {
                int len = max(0, height[rak[i-1]] - 1);
                int p1 = i + len, p2 = sa[rak[i]-1] + len;
                while (a1[p1++] == a1[p2++]) len++;
                height[rak[i]] = len;
            }
        }
}SA;
 
class Number_Theoretic_Transform{
    int pos[M],REV,G;
    public:
        inline void init() {
            for (L=1;L<n+m;L<<=1); G = 3;
            int len = 1,tt=-1; while (len < L) len<<=1, ++tt; REV = Pow(L, MOD-2);
            for (int i=1;i<len;i++) pos[i] = (pos[i>>1]>>1)|((1<<tt)*(i&1));
        }
        inline void trans(int *a, int t=1) {
            for (int i=0;i<L;i++) if (pos[i] < i) swap(a[pos[i]], a[i]);
            for (int l=2;l<=L;l<<=1) {
                int wn = Pow(G, MOD/l); if (t == -1) wn = Pow(wn, MOD-2);
                for (int i=0;i<L;i+=l) {
                    for (int j=0,w=1;j<l/2;j++,w=(LL)w*wn%MOD) {
                        int tmp = (LL)w * a[i+l/2+j] % MOD;
                        a[i+l/2+j] = (a[i+j] - tmp) % MOD;
                        a[i+j] = (a[i+j] + tmp) % MOD;
                    }
                }
            }
            if (t == -1) for (int i=0,rev=Pow(L,MOD-2);i<L;i++) a[i] = (LL)a[i] * rev % MOD; 
            for (int i=0;i<L;i++) a[i] = a[i]<0? a[i] + MOD: a[i];
        } 
    private:
        inline int Pow(int w, int t) {
            int ret = 1;
            for (;t;t>>=1,w=(LL)w*w%MOD)
                if (t&1) ret=(LL)ret*w%MOD;
            return ret;
        }
}NTT;
 
int main() {
    n = read(); m = read();
    for (int i=1;i<=n;i++) a1[i] = o1[i] = Read();
    for (int i=1;i<=m;i++) a2[i] = o2[i] = Read();
     
    //find out legal positions
    for (int i=1;i<=m;i++) a1[n+i+1] = a2[i];
    for (int i=1;i<=n+m+1;i++) a1[i] >>= 1, a1[i]++;
    a1[n+1] = 0; SA.build(); 
    SA.solve();
     
    //calculate the cost
    NTT.init();
    memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2));
    for (int i=0;i<n;i++) a1[i] = o1[i+1] & 1;
    for (int i=0;i<m;i++) a2[i] = (o2[m-i] & 1) ^ 1;
    NTT.trans(a1); NTT.trans(a2);
    for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD;
    NTT.trans(a1, -1);
    for (int i=1;i<=n;i++) ans[i] = a1[i+m-2];
    memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2));
    for (int i=0;i<n;i++) a1[i] = (o1[i+1] & 1) ^ 1;
    for (int i=0;i<m;i++) a2[i] = o2[m-i] & 1;
    NTT.trans(a1); NTT.trans(a2);
    for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD;
    NTT.trans(a1, -1);
    for (int i=1;i<=n;i++) ans[i] += a1[i+m-2];
     
    //output the answer
    int pos=-1, cost=INF;
    for (int i=1;i<=n;i++) if (leg[i] && ans[i] < cost) cost = ans[i], pos = i;
    if (!~pos) puts("No");
    else printf("Yes\n%d %d\n",cost,pos);
    return 0;
}

【日常小测】Circle of Stones

题目大意

给定$(n \le 10^6)$个石头,它们排成一圈
每个石头上有一个小写英文字母
定义优雅为任意两个相邻的石头上的字母不同
请你输出$n$个数(0/1),第$i$个数表示删除$i-1$个连续的石头能否使原来的圈成为优雅的圈
每个测试点包含$T(1 \le T \le 6)$组数据

解题报告

我们先来解决一个子问题:如果给定一个优雅的长度为$n$的圈$A$,问保留能否选择连续的$1 \sim n$个石头,使之优雅
考虑长度为$l$的询问,那么左端点和右端点的可行解都是一段长度为$n-l+1$的前缀/后缀
如果这两段区间不完全相等(不是原串的循环节),那么肯定可以把不等的那一位拿出来作为可行解
于是我们用$KMP$求一个循环节就可以了

现在我们再来看原问题,考虑原串中相邻的两位$i,i+1$和右边一次相邻的两位$j,j+1$
显然我们至多保留$[i+1,j]$这一串
那么这一串此时已经是优雅的了,于是就成了刚刚我们讨论的子问题
于是找出每一个极大的优雅子串,跑一边$KMP$更新答案,最后输出即可
时间复杂度:$O(Tn)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 2000009;
 
int n,nxt[N],vis[N];
char pat[N],ans[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline bool SPJ() {
    if (pat[n] == pat[1]) return 0;
    for (int i=2;i<=n;i++) if (pat[i] == pat[i-1]) return 0;
    return 1;
}
 
inline int cyc(int l, int r) {
    nxt[1] = 0; 
    for (int w=0,i=l+1;i<=r;i++) {
        while (w && pat[w+l] != pat[i]) w = nxt[w];
        if (pat[w+l] == pat[i]) w++;
        nxt[i-l+1] = w;
    } int len = r - l + 1;
    if (nxt[len] &&len % (len - nxt[len]) == 0) return len - nxt[len];
    else return 0;
}
 
inline void update(int l, int r) {
    static int id = 1; id++;
    int lop = cyc(l, r), len = r - l + 1;
    for (int w=nxt[len];w;w=nxt[w]) vis[w] = id;
    for (int i=1,lim=min(len,n);i<=lim;i++) 
        if (vis[len-i+1]!=id) ans[n-i] = '1';
}
 
int main() {
    for (int t=1,lop;~scanf("%s",pat+1);++t) {
        n = strlen(pat+1); printf("Case %d: ",t);
        for (int i=0;i<n;i++) ans[i] = '0';
        ans[n] = 0; ans[n - 1] = '1';  
        memcpy(pat+n+1, pat+1, sizeof(char)*n);
        if (SPJ()) update(1, n<<1);
        else {
            int pre = 0;
            for (int i=n<<1;i;i--) {
                if (pat[i] == pat[i+1]) {
                    if (i < n) update(i+1, pre);
                    pre = i;
                }
            }
            if (pre && pat[1] == pat[n] && n > 1) update(1, pre);
        }
        puts(ans);
    }
    return 0;
}

【BZOJ 4641】基因改造

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4641
神犇题解:http://blog.csdn.net/neither_nor/article/details/52218134

解题报告

据说可以KMP,具体可以看这里:传送门
不过,考虑一个更优美的做法:

这题显然可以转化为带通配符的字符串匹配问题
于是我们再撸一发FFT就可以了!

什么?复杂度过不去?
那我也没办法 _(:з」∠)_

【HDU 5442】Favorite Donut

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5442
数据生成器:http://paste.ubuntu.com/18084370/

这题,SA可做,SAM可做,最小表示法可做
然而我的SA对拍怎么都过不了,本地不错,交上去就wa,弃疗

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

const int MAXN = 1600000+9;
const int SIGMA_SIZE = 30;

char pat[MAXN];
int n;

namespace Suffix_Array{
	#define SA Suffix_Array
	int sa[MAXN],height[MAXN],bot[MAXN];
	int t1[MAXN],t2[MAXN],*tmp,*rank;
	int m,cnt,Pos[MAXN],ord[MAXN],wor[MAXN];
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) height[i] = 0;
		for (int i=1;i<=n;i++) if (rank[i] > 1){
			int sta = max(0,height[rank[i-1]]-2);
			int p1 = i+sta, p2 = sa[rank[i]-1]+sta;
			while (pat[p1++] == pat[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		memset(bot,0,sizeof(bot));
		memset(height,0,sizeof(height));
		
		tmp = t1; rank = t2;
		n = strlen(pat+1); m = SIGMA_SIZE;
		for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+2]++;
		for (int i=2;i<=m;i++) bot[i] += bot[i-1];
		for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++)
			if (tmp[sa[i]]==tmp[sa[i-1]]) rank[sa[i]] = m;
			else rank[sa[i]] = ++m;
			
		for (int k=1;k<=n;k*=2){int T=0;
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i]>k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
			
			swap(rank, tmp);
			rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++) if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]] = m; else rank[sa[i]] = ++m; if (m >= n) break;
		}
		
		GetHeight();
	}
	
	inline bool sort_cmp(const int a, const int b){
		if (Pos[a] != Pos[b]) return Pos[a] < Pos[b];
		else return wor[a] < wor[b]; } inline bool judge(int i, int pos){ if ((pos>=1&&pos<=n/4) || (pos>=n/2+2&&pos<=n/2+n/4+1)){ cnt=1; if (pos>=1&&pos<=n/4) Pos[cnt]=pos, wor[cnt]=0; else Pos[cnt]=n/2+n/4+2-pos, wor[cnt]=1; while (height[i--] >= n/4){
				pos = sa[i];
				if (pos>=1&&pos<=n/4) Pos[++cnt]=pos, wor[cnt]=0; else if (pos>=n/2+2&&pos<=n/2+n/4-1) Pos[++cnt]=n/2+n/4+2-pos, wor[cnt]=1;
			}
			
			for (int j=1;j<=cnt;j++) ord[j] = j; sort(ord+1,ord+1+cnt,sort_cmp); printf("%d %d\n",Pos[ord[1]],wor[ord[1]]); return true; } else return false; } inline void solve(){ for (int i=n;i;i--) if (judge(i,sa[i])) break; } }; int main(){ int T; cin>>T;
	while (T--){
		scanf("%d%s",&n,pat+1); 
		for (int i=1;i<=n;i++) pat[n+i] = pat[i]; n *= 2;
		for (int i=1;i<=n;i++) pat[n+i+1] = pat[n-i+1];
		pat[n+1] = 'a'-1; n=n*2+1; pat[n+1] = 0;
		SA::build();
		SA::solve();
	}	
	return 0;
}

【BZOJ NOI十连测】KMP

题目传送门:http://begin.lydsy.com/JudgeOnline/problem.php?id=3026
离线版题目:http://paste.ubuntu.com/18022623/
数据生成器:http://paste.ubuntu.com/18021204/
大样例答案:http://paste.ubuntu.com/18022708/
大样例:http://paste.ubuntu.com/18022662/

这是一道很好玩的题目!本来以为是字符串处理题目,结果最后是图论QAQ
很明显,nxt[]实际上是给出了一些字符的等于或不等关系。
如果我们把不等关系用边来表示,那么这货就是一个弦图。
证明的话,也很简单:因为所连的边一定是一条fail链上拓展出来的,所以每一次连边,一定会向所有可能建立关系的点连边
这样的话,不仅仅是一个弦图?还是一个完全图?
然后用完美消除序列倒着求方案数乘一乘就好。(参见本博客的文章《弦图的计数问题》)

更进一步,kmp的构造顺序就是反的完美消除序列。
这个的证明建立在上文提到的“一定会向所有可能建立关系的点连边”,即每一次如果加入了点,那么这个点是一个单纯点
所以直接按照数组顺序乘就可以了QAQ

弦图染色代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define LL long long
using namespace std;

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

const int MAXN = 200000+9;
const LL MOD = 1000000000+7;

int n,c,cnt,fail[MAXN],p[MAXN],Ord[MAXN];
int T,nxt[MAXN],head[MAXN],to[MAXN];
int tot,mx,used[MAXN],pos[MAXN],ord[MAXN];
queue<int> que[MAXN];

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline void MCS(){
	tot = 0; mx = 0;
	for (int i=1;i<=n;i++)
		que[0].push(i);
		
	while (tot < n){
		while (!que[mx].empty()&&used[que[mx].front()]) 
			que[mx].pop();
		if (que[mx].empty()) mx--;
		else {
			int w = que[mx].front(); que[mx].pop();
			ord[++tot] = w; used[w] = 1;
			for (int i=head[w];i;i=nxt[i]) if (!used[to[i]]) 
				que[++pos[to[i]]].push(to[i]), 
				mx = max(mx, pos[to[i]]);
		}
	}
}

int main(){
	n = read(); c = read();
	for (int i=2;i<=n;i++) fail[i] = read();
	
	p[1] = cnt = 1;
	for (int i=1,j;i<n;i++){
		if (fail[i+1]) p[i+1]=p[fail[i+1]];
		else {
			int j = fail[i]; p[i+1]=++cnt;
			while (j) {
				if (Ord[p[j+1]] < i+1 ) 
					AddEdge(p[j+1],p[i+1]), Ord[p[j+1]]=i+1; 
				j=fail[j];
			}
			if (Ord[p[j+1]] < i+1 ) 
				AddEdge(p[j+1],p[i+1]), Ord[p[j+1]]=i+1; 
		}
	}
	
	MCS();
	
	LL vout = 1;
	memset(used,0,sizeof(used));
	for (int j=1,i=ord[j],sum;j<=cnt;i=ord[++j]){
		sum = 0; 
		for (int k=head[i];k;k=nxt[k])
			if (used[to[k]]) sum++;
		sum = c-sum; used[i] = 1;
		vout = (vout*(LL)sum)%MOD;
	}
	printf("%lld\n",vout);
	
	return 0;
}

%%% YJQ 的利用kmp特殊性质的神代码:

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const LL MOD = 1000000000+7;
const int MAXN = 200000+9;
int n,m,fail[MAXN],go[MAXN];

int main(){
	cin>>n>>m;
	for (int i=2;i<=n;i++)
		scanf("%d",&fail[i]);
	go[0]=1; int ans=m;
	for (int i=1;i<n;i++){
		if (fail[i+1]) go[i] = go[fail[i]];
		else go[i] = go[fail[i]]+1,
		ans = 1LL*ans*(m-go[fail[i]])%MOD;
	}
	printf("%d\n",ans);
	return 0;
}

【BZOJ 3620】似乎在梦中见过的样子

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3620
离线版题目:http://paste.ubuntu.com/17950176/

求字串的前缀和后缀相等。WTF,这不14年的动物园吗?
又用到KMP的fail_chain就是从大到小遍历原串前缀的前后缀相等长度
然后O(n^2)暴力
1A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

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

const int MAXN = 15000+9;

char pat[MAXN];
int fail[MAXN],vout,N,k;

inline void solve(char *s, int n){
	fail[0] = fail[1] = 0;
	for (int i=2,j=0;i<=n;i++){
		while(j && s[j+1] != s[i]) j = fail[j];
		if (s[j+1] == s[i]) j++;
		fail[i] = j;
	}
	for (int i=k*2+1,t=i;i<=n;i++,t=i) { while ((fail[t])*2+1 > i) t = fail[t];
		if (fail[t] >= k) vout++; 
	}
}

int main(){
	scanf("%s%d",pat+1,&k);
	N = strlen(pat+1);
	for (int i=1;i<=N-k*2;i++)
		solve(pat+i-1,N+1-i);
	printf("%d\n",vout);
	return 0;
}

其实之前想了一想,貌似SA有希望在O(n)的时间复杂度内解决?
搞出sa[]之后,上下以k为限制扫一扫,统计统计。但这样时间复杂度我只能证到是O(n^2)的,还常数还比KMP大

【BZOJ 3670】[Noi2014] 动物园

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3670
离线版题目:http://paste.ubuntu.com/17902051/

想了很久。最后觉得SAM+链剖+主席树可捉,一看数据范围,这个有问题啊!
于是可耻的看了题解,我再也不敢说KMP简单了,MD小性质有一堆QAQ
干货写在《KMP总结》里,这里只扔一份代码吧!

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const LL MOD = 1000000007;

char pat[MAXN];
int n,fail[MAXN],cnt[MAXN];

int main(){
	int T; cin>>T;
	while (T--){
		scanf("%s",pat+1);
		n = strlen(pat+1); cnt[1] = 1;
		for (int i=2,j=0;i<=n;i++){
			while (j && pat[j+1] != pat[i]) j = fail[j];
			if (pat[j+1] == pat[i]) j++;
			fail[i] = j; cnt[i] = cnt[fail[i]] + 1;
		} LL vout = 1;
		for (int i=2,j=0;i<=n;i++){ while (j && pat[j+1] != pat[i]) j = fail[j]; if (pat[j+1] == pat[i]) j++; while (j && j*2 > i) j = fail[j];
			vout = (vout*(cnt[j]+1)) % MOD;
		}
		printf("%d\n",int(vout));
	}
	return 0;
} 

【BZOJ 1355】[Baltic2009]Radio Transmission

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1355
离线版题目:http://paste.ubuntu.com/17890900/

这一道题目,让我有一种自杀的冲动QAQ
先是想:嗯,SA的话O(nlogn)应该能过,于是开开心心去写SA
然而都快写完了,突然发现:WTF!被卡内存了
于是想KMP,总算回忆起那个神奇的结论,于是又写KMP,结果还写挂啦QAQ
不说了,说的了都是泪QAQ
本来是一道水题,结果做了俩小时QAQ

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

const int MAXN = 2000000+9;

char pat[MAXN];
int nxt[MAXN],n;

int main(){
	scanf("%d%s",&n,pat+1);
	
	for (int i=2,j=0;i<=n;i++){
		while (j&&pat[j+1] != pat[i]) j=nxt[j];
		if (pat[j+1]==pat[i]) j++;
		nxt[i] = j; 
	}
	
	printf("%d\n",n-nxt[n]);
	
	return 0;
} 

好吧,我承认这题还是比较好玩的。以前以为Kmp的那个结论只有整除的时候才能用。
刚刚证了证发现非整除也可以用QAQ
另外%这位大神,用hash把内存给省下去了:http://blog.csdn.net/wzq_qwq/article/details/49005295
我hash果然还是弱得完全没法用