【poj3415-Common Substrings】sam子串计数
题意: 给出两个串，问这两个串的所有的子串中（重复出现的，只要是位置不同就算两个子串），长度大于等于k的公共子串有多少个。
题解：
这题好像大神们都用后缀数组做。。然而我在sam的题表上看到这题，做了一百年才做出来。。还看了题解好吗。。
先对第一个串构造 SAM,逆拓扑序求出right存入r[]。
某个节点的right集合表示Min(x)~Max(x)这一段子串都出现了r[x]次
用第二个串对 SAM 做 LCS，当前节点x LCS>=K时，ans+=ans+=r[x]*(len-maxx(k,step[pre[x]]+1)+1);（当前匹配的最长串的子串数）。
如果step[pre[x]]>=k,cnt[pre[x]]++;
比如样例:（k=1）
xx
xx
我给它们编号
x1 x2
x3 x4
那么跑串2的x3的时候跑到了sam上的x1节点，ans++；
但是x2也可以跟x3匹配呀
跑到x4的时候，sam跑到了x2
我们可以在x2的pre也就是x1上打个标记，以后加上去。
用字符串A构造SAM，在SAM上匹配第二个字符串B，设当前匹配长度为len，且位于状态p，则当前状态中满足条件长度不小于K的公共子串的字符串个数为
sum = len-max{ K,Min(p) }+1
SAM中一个状态代表的字符串长度为一个连续区间[ Min(s),Max(s) ]，Min(s)为最小长度。
这些字符串重复的次数为|right|，即right集的大小，可以递推得到，则当前状态对于答案的贡献为sum*|right|
这时候匹配的是p，还应该统计parent树中p->root的路径上的状态中满足条件的个数。
这里设一个懒标记tag[x]，记录节点x需要统计的次数，最后算一遍，每次如果Max(p->fa) >= K则上传标记。
需要注意的是可能出现大写字符 =_=
相比较而言SAM的做法更好想一些。
---------------------------------------------------------------------http://www.cnblogs.com/lidaxin/p/5005079.html
拓扑序逆序统计不是最长公共子串的状态但是被子串包含的个数，ans+=cnt[p]*(step[p]- max(K,Min(p)+1)*r[p]，同时维护cnt:cnt[pre[p]]+=cnt[p]。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 #include<ctime>
7 #include<algorithm>
8 using namespace std;
9
10 typedef long long LL;
11 const int N=2*100010,S=52;
12 int k,tot,last,al,bl,cl;
13 int son[N][30],pre[N],step[N],in[N],c[N],r[N],cnt[N];
14 char a[N],b[N];
15 bool vis[N];
16 queue<int> Q;
17
18 int minn(int x,int y){return x<y ? x:y;}
19 int maxx(int x,int y){return x>y ? x:y;}
20
21 int idx(char ch)
22 {
23 if(ch>='a' && ch<='z') return ch-'a'+1;
24 return ch-'A'+1+26;
25 }
26
27 int add_node(int x)
28 {
29 step[++tot]=x;
30 return tot;
31 }
32
33 void clear()
34 {
35 memset(r,0,sizeof(r));
36 memset(cnt,0,sizeof(cnt));
37 memset(son,0,sizeof(son));
38 memset(pre,0,sizeof(pre));
39 memset(step,0,sizeof(step));
40 tot=0;add_node(0);last=1;
41 }
42
43 void extend(int ch)
44 {
45 int p=last,np=add_node(step[last]+1);
46 while(p && !son[p][ch]) son[p][ch]=np,in[np]++,p=pre[p];
47 if(!p) pre[np]=1;
48 else
49 {
50 int q=son[p][ch];
51 if(step[q]==step[p]+1) pre[np]=q;
52 else
53 {
54 int nq=add_node(step[p]+1);
55 memcpy(son[nq],son[q],sizeof(son[q]));
56 for(int i=0;i<=9;i++)
57 if(son[q][i]) in[son[q][i]]++;
58 pre[nq]=pre[q];
59 pre[np]=pre[q]=nq;
60 while(son[p][ch]==q) in[q]--,in[nq]++,son[p][ch]=nq,p=pre[p];
61 }
62 }
63 last=np;
64 }
65
66 void find_tp()
67 {
68 while(!Q.empty()) Q.pop();
69 Q.push(1);vis[1]=1;cl=0;
70 while(!Q.empty())
71 {
72 int x=Q.front();vis[x]=0;c[++cl]=x;Q.pop();
73 for(int i=1;i<=26;i++)
74 {
75 int y=son[x][i];
76 if(!y) continue;
77 in[y]--;
78 if(!in[y] && !vis[y]) vis[y]=1,Q.push(y);
79 }
80 }
81 }
82
83 void find_right()
84 {
85 int x=1,ch;
86 for(int i=1;i<=al;i++)
87 {
88 ch=idx(a[i]);
89 x=son[x][ch];
90 r[x]++;
91 }
92 for(int i=cl;i>=1;i--) r[pre[c[i]]]+=r[c[i]];
93 }
94
95 int main()
96 {
97 freopen("a.in","r",stdin);
98 int x,ch,len,ans;
99 while(1)
100 {
101 scanf("%d",&k);
102 if(!k) return 0;
103 scanf("%s%s",a+1,b+1);
104 al=strlen(a+1);
105 bl=strlen(b+1);
106 clear();
107 for(int i=1;i<=al;i++) extend(idx(a[i]));
108 find_tp();
109 find_right();
110 // for(int i=1;i<=cl;i++) printf("%d ",c[i]);printf("
");
111 // for(int i=1;i<=tot;i++) printf("r %d = %d
",i,r[i]);
112 x=1,len=0;
113 LL ans=0;
114 for(int i=1;i<=bl;i++)
115 {
116 ch=b[i]-'a'+1;
117 while(x && !son[x][ch]) x=pre[x],len=step[x];
118 x=son[x][ch];len++;
119 if(x==0) x=1,len=0;
120 if(len>=k)
121 {
122 cnt[x]++;
123 ans+=r[x]*(len-maxx(k,step[pre[x]]+1)+1);
124 }
125 }
126 for(int i=cl;i>=1;i--) cnt[pre[c[i]]]+=cnt[c[i]];
127 for(int i=2;i<=tot;i++)
128 {
129 int fa=pre[i];
130 if(!fa) continue;
131 if(step[fa]>=k) ans+=cnt[i]*(step[fa]-maxx(k,step[pre[fa]])+1)*r[fa];
132 }
133 printf("%lld
",ans);
134 }
135 return 0;
136 }