首页 > 代码库 > UVA 10679 I Love Strings

UVA 10679 I Love Strings

2024-08-11 04:32:48   217人阅读

传送门

题目大意

给定文本串$S$和若干模式串$\{T\}$, 对每个模式串$T$, 询问$T$是否为$S$的字串.

Solution

裸的AC自动机, 也可以用后缀数组做.

P.S. 这题数据很弱, 朴素的字符串匹配也能过.

Pitfalls

模式串有重复的. 这样, 在建TRIE时就不能直接对每个模式串对应的节点 (尾节点) 标记上模式串的序号, 否则对于重复出现的模式串, 最后一次出现的那个会把在它之前的那些覆盖掉.

正确的做法是, 对于每个尾节点作唯一标号. 另外维护一个表$idx[]$, $idx[i]$表示第$i$个模式串的尾节点的标号.

另外要注意AC自动机的某些易错的实现细节, 代码注释有提及.

Implementation

注释比较详细, 可作为模板.

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 const int N{1<<20}, M{1<<10}; 5  6 bool res[M]; 7 int idx[M]; 8 char s[N], t[M]; 9 int ch[N][52], id[N], fail[N], last[N];10 11 12 int get_id(char ch){13     return islower(ch)?ch-‘a‘:ch-‘A‘+26;14 }15 16 queue<int> que;17 18 int main(){19     // cout<<int(‘a‘)<<‘ ‘<<int(‘z‘)<<‘ ‘<<int(‘A‘)<<‘ ‘<<int(‘Z‘)<<endl;20     int T;21     for(cin>>T; T--; ){22         int q;23         scanf("%s%d", s, &q);24         int tail=0;25 26         memset(res, false, sizeof(res));    //error-prone27 28         memset(ch[tail], 0, sizeof(ch[tail]));29         tail++;30 31         for(int i=1; i<=q; i++){32             scanf("%s", t);33             int u=0;34             for(int j=0; t[j]; j++){35                 int &v=ch[u][get_id(t[j])];36                 if(!v){37                     v=tail++;38                     memset(ch[v], 0, sizeof(ch[v]));39                     id[v]=0;40                 }41                 u=v;42             }43             if(!id[u]) id[u]=i; //error-prone: possibly duplicate patterns44             idx[i]=id[u];45         }46 47         for(int i=0; i<52; i++){48             int u=ch[0][i];49             if(u){50                 que.push(u);51                 fail[u]=last[u]=0;  //error-prone, must be initialized!!52             }53         }54 55         for(; que.size(); ){56             int u=que.front();57             que.pop();58             for(int i=0; i<52; i++){59                 //!view a variable (object) as an entity60                 int &v=ch[u][i];61                 if(v){  //v is a new node, construct a new node of AC automata62                     que.push(v);63                     //no need to init. last[] and fail[], as they are is induced.64                     fail[v]=ch[fail[u]][i];65                     last[v]=id[fail[v]]?fail[v]:last[fail[v]];66                 }67                 else{   //the expected node v does not exist68                     v=ch[fail[u]][i];69                 }70             }71         }72 73         for(int i=0, u=0; s[i]; i++){74             u=ch[u][get_id(s[i])];75             res[id[u]]=true;76             for(int v=last[u]; v; res[id[v]]=true, v=last[v]);  //error-prone77         }78 79         for(int i=1; i<=q; i++)80             puts(res[idx[i]]?"y":"n");81         82     }83 }

 

上穷碧落下黄泉.

 

UVA 10679 I Love Strings


联系
我们