hihocoder 1465 循环串匹配问题（后缀自动机）-白红宇

hihocoder 1465 循环串匹配问题（后缀自动机）

阅读量：6183 次

发布时间：2019-06-21

本文共 2852 字，大约阅读时间需要 9 分钟。

后缀自动机感觉好万能

tries图和ac自动机能做的，后缀自动机很多也都可以做

这里的循环匹配则是后缀自动机能做的另一个神奇功能

循环匹配意思就是S是abba， T是abb

问'abb', 'bba','bab'在S中出现过多少次。

我们先把T的末尾循环加一遍，变成abbab

然后把问题转换成，求T的每个后缀和S的最长公共子串

如果最长公共子串的长度大于等于T的长度，那么就说明这个后缀匹配成功

做法就是先对S建立一个后缀自动机，然后记录一个状态

(u, l)，u表示当前在后缀自动机匹配的位置，l表示最长公共子串的长度

考虑转移的话，就是

如果下一个位置可以匹配，那么u就到相应的位置，l = l+1

答案更新的时候要注意，如果l大于T的长度len，就需要顺着link往前走到第一个能匹配的位置，即第一个maxlen[x] >= len的地方，然后答案加上endpos[x]，不然会丢一部分答案。

如果下一个位置不可以匹配，那么u就顺着link边走，走到第一个能匹配的地方，如果找不到，那u就设成起点，l为0

还有一个问题就是串重复的情况，比如说T是aa，那么扩充就会变成aaa，aa和aa重复。

如果串重复的话，那么必定会到同一个状态，所以一个状态标记一下，只更新一遍答案就可以了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;int n = 0, len, st;const int maxL = 1e6 + 100;int maxlen[2*maxL], minlen[2*maxL], trans[2*maxL][27], slink[2*maxL], lab[2*maxL], son[2*maxL], endpos[2*maxL];map
          
            vis;int new_state(int _maxlen, int _minlen, int *_trans, int _slink){ maxlen[n] = _maxlen; minlen[n] = _minlen; for(int i = 0; i < 26; i++){ if(_trans == NULL) trans[n][i] = -1; else trans[n][i] = _trans[i]; } slink[n] = _slink; return n++;}int add_char(char ch, int u){ int c = ch - 'a'; int z = new_state(maxlen[u]+1, -1, NULL, -1); lab[z] = 1; int v = u; while(v != -1 && trans[v][c] == -1){ trans[v][c] = z; v = slink[v]; } if(v == -1){ minlen[z] = 1; slink[z] = 0; return z; } int x = trans[v][c]; if(maxlen[v] + 1 == maxlen[x]){ minlen[z] = maxlen[x] + 1; slink[z] = x; return z; } int y = new_state(maxlen[v] + 1, -1, trans[x], slink[x]); slink[y] = slink[x]; minlen[x] = maxlen[y] + 1; slink[x] = y; minlen[z] = maxlen[y] + 1; slink[z] = y; int w = v; while(w != -1 && trans[w][c] == x){ trans[w][c] = y; w = slink[w]; } minlen[y] = maxlen[slink[y]] + 1; return z;}char str[maxL];int main(){ cin>>str; st = new_state(0, 0, NULL, -1); int len = strlen(str); for(int i = 0; i < len; i++) { st = add_char(str[i], st); } for(int i = 1; i <= n; i++) son[slink[i]]++; queue
           
             Q; for(int i = 1; i <= n; i++) if(son[i] == 0) Q.push(i), endpos[i] = 1; while(!Q.empty()){ int x = Q.front(); Q.pop(); if(x == 0) continue; int y = slink[x]; son[y]--; endpos[y] += endpos[x]; if(son[y] == 0){ if(lab[y]) endpos[y]++; Q.push(y); } } int T; cin>>T; while(T--){ vis.clear(); cin>>str; int len = strlen(str), ylen = len; for(int i = len; i < 2*len-1; i++) str[i] = str[i-len]; len = 2*len-1; int u = 0, l = 0, ans = 0; for(int i = 0; i < len; i++){ int c = str[i] - 'a'; if(trans[u][c] != -1){ u = trans[u][c]; l++; } else { int y = slink[u]; while(y != -1){ if(trans[y][c] != -1){ l = maxlen[y] + 1; u = trans[y][c]; break; } u = y; y = slink[u]; } if(y == -1) { u = 0; l = 0; } } if(l >= ylen){ int y = slink[u]; while(maxlen[y] >= ylen) { u = y; y = slink[u]; l = maxlen[u]; } if(vis[u]) continue; vis[u] = 1; ans += endpos[u]; } } cout<
            
             <