Chlience

【题解】HIHOCODER 1465 后缀自动机五·重复旋律8
Problem传送门 >ω<题目大意:给定模式串 $s$ , $n$ 个匹配串 $str_i$求每个匹配串的循环同...
扫描右侧二维码阅读全文
13
2018/10

【题解】HIHOCODER 1465 后缀自动机五·重复旋律8

Problem

传送门 >ω<

题目大意:

给定模式串 $s$ , $n$ 个匹配串 $str_i$
求每个匹配串的循环同构能够匹配的子串总数

Solution

求循环同构的匹配,首先第一步应该是将匹配串倍长,再进行匹配,这样就能得到匹配串所有循环同构

但是发现一个匹配串的循环同构可能会相同,而不能计算重复的匹配

如何实现?

对于每个匹配串的每个位置,都能求出模式串中的最长匹配前缀
如果匹配串某个位置的匹配长度超过了原匹配串长度,就说明以该位置为结尾字符的串一定能够与模式串匹配

但是当前状态并不一定包含原串的循环同构(长度太长),所以需要通过 $fa$ 找到包含原串长度的状态,并且标记即可(防止重复)

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
char s[N];
struct SAM {
    int ch[N << 1][26] , fa[N << 1] , l[N << 1] , siz[N << 1];
    int bac[N] , T[N  << 1];
    int vis[N << 1];
    int cnt , last;
    void ins(int c) {
        int x = last , nx = ++ cnt; last = nx;
        l[nx] = l[x] + 1; siz[nx] = 1;
        for(; x && !ch[x][c] ; x = fa[x]) ch[x][c] = nx;
        if(!x) fa[nx] = 1;
        else {
            int y = ch[x][c];
            if(l[y] == l[x] + 1) fa[nx] = y;
            else {
                int ny = ++ cnt; l[ny] = l[x] + 1;
                memcpy(ch[ny] , ch[y] , sizeof(ch[y]));
                fa[ny] = fa[y]; fa[y] = fa[nx] = ny;
                for(; x && ch[x][c] == y ; x = fa[x]) ch[x][c] = ny;
            }
        }
    } 
    void insert(char *s) {
        cnt = last = 1;
        int len = strlen(s);
        for(int i = 0 ; i < len ; ++ i) ins(s[i] - 'a');

        for(int i = 1 ; i <= cnt ; ++ i) ++ bac[l[i]];
        for(int i = 1 ; i <= len ; ++ i) bac[i] += bac[i - 1];
        for(int i = 1 ; i <= cnt ; ++ i) T[bac[l[i]] --] = i;
        for(int i = cnt ; i ; -- i) siz[fa[T[i]]] += siz[T[i]];
    }
    void cal(char * s , int qwe) {
        int n = strlen(s) , c  , m = n * 2 - 1;
        int x = 1 , lenth = 0 , ans = 0;
        for(int i = 0 , h = 0 ; i < n * 2 - 1 ; ++ i , ++ h) {
            if(h >= n) h -= n;
            c = s[h] - 'a';
            while(x && !ch[x][c]) {x = fa[x]; lenth = l[x];}
            if(ch[x][c]) {x = ch[x][c]; ++ lenth;}
            else {x = 1; lenth = 0;}
            if(lenth > n) while(l[fa[x]] >= n) {x = fa[x]; lenth = l[x];}
            if(lenth >= n && vis[x] != qwe) {vis[x] = qwe; ans += siz[x];}
        }
        printf("%d\n" , ans);
    }
}sam;
int main() {
    scanf("%s" , s);
    sam.insert(s);
    int t = read();
    for(int i = 1 ; i <= t ; ++ i) {
        scanf("%s" , s);
        sam.cal(s , i);
    }
    return 0;
}
Last modification:October 13th, 2018 at 10:50 pm

Leave a Comment