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

后缀自动机感觉好万能

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 <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#include <map>

using namespace std;

int n = , len, st;

const int maxL = 1e6 + ;

int maxlen[*maxL], minlen[*maxL], trans[*maxL][], slink[*maxL], lab[*maxL], son[*maxL], endpos[*maxL];

map<int, bool> vis;

int new_state(int _maxlen, int _minlen, int *_trans, int _slink){

    maxlen[n] = _maxlen;

    minlen[n] = _minlen;

    for(int i = ; i < ; i++){

        if(_trans == NULL)

            trans[n][i] = -;

        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]+, -, NULL, -); lab[z] = ;

    int v = u;

    while(v != - && trans[v][c] == -){

        trans[v][c] = z;

        v = slink[v];

    }

    if(v == -){

        minlen[z] = ;

        slink[z] = ;

        return z;

    }

    int x = trans[v][c];

    if(maxlen[v] +  == maxlen[x]){

        minlen[z] = maxlen[x] + ;

        slink[z] = x;

        return z;

    }

    int y = new_state(maxlen[v] + , -, trans[x], slink[x]);

    slink[y] = slink[x];

    minlen[x] = maxlen[y] + ;

    slink[x] = y;

    minlen[z] = maxlen[y] + ;

    slink[z] = y;

    int w = v;

    while(w != - && trans[w][c] == x){

        trans[w][c] = y;

        w = slink[w];

    }

    minlen[y] = maxlen[slink[y]] + ;

    return z;

}

char str[maxL];

int main()

{

    cin>>str;

    st = new_state(, , NULL, -);

    int len = strlen(str);

    for(int i = ; i < len; i++) {

        st = add_char(str[i], st);

    }

    for(int i = ; i <= n; i++) son[slink[i]]++;

    queue<int> Q;

    for(int i = ; i <= n; i++) if(son[i] == ) Q.push(i), endpos[i] = ;

    while(!Q.empty()){

        int x = Q.front(); Q.pop();

        if(x == ) continue;

        int y = slink[x];

        son[y]--; endpos[y] += endpos[x];

        if(son[y] == ){

            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 < *len-; i++) str[i] = str[i-len];

        len = *len-;

        int u = , l = , ans = ;

        for(int i = ; i < len; i++){

            int c = str[i] - 'a';

            if(trans[u][c] != -){

                u = trans[u][c];

                l++;

            } else {

                int y = slink[u];

                while(y != -){

                    if(trans[y][c] != -){

                        l = maxlen[y] + ;

                        u = trans[y][c];

                        break;

                    }

                    u = y;

                    y = slink[u];

                }

                if(y == -) { u = ; l = ; }

            }

            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] = ;

                ans += endpos[u];

            }

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

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

最新文章

热门文章