2020-2021:teams:legal_string:王智彪:序列自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:序列自动机 [2021/08/01 18:42] 王智彪 |
2020-2021:teams:legal_string:王智彪:序列自动机 [2021/08/01 19:25] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 25: | 行 25: | ||
| <code cpp> | <code cpp> | ||
| - | struct SQAM {//构建复杂度是n方的 | + | struct SQAM { |
| - | int ch[MAXL][MAXM],las[MAXM],pre[MAXL]; | + | int ch[MAXL][MAXM],las[MAXM]; |
| - | int root,tot; | + | int root; |
| void init() { | void init() { | ||
| - | root=tot=1; | + | root=1;//构造根节点 |
| - | for(int i=0; i<MAXM; i++) las[i]=1; //上一个是根节点 | + | |
| } | } | ||
| - | void insert(int c) { | + | void work(char s[]) { |
| - | int p=las[c],np=++tot;//p是上一个字符c出现的结点 np是现在结点 | + | int len=strlen(s); |
| - | pre[np]=p;//现在结点的前驱是上一个出现的结点 | + | for(int i=len-1;i>=0;i--) { |
| - | for(int i=0; i<MAXM; i++) { //对于每个字符对于字符c都要更新下一次出现的位置 | + | for(int j=0;j<MAXM;j++) ch[i+2][j]=las[j];//每个字符是一个节点 根节点是1 所以0位置字符状态为2 |
| - | for(int j=las[i]; j&&!ch[j][c]; j=pre[j]) { //这个位置没有接过c，这次接上 然后一直跳pre都更新 | + | las[s[i]-'a']=i+2; |
| - | ch[j][c]=np; | + | |
| - | } | + | |
| } | } | ||
| - | las[c]=np;//别忘了把最新的位置更新 | + | for(int i=0;i<MAXM;i++) ch[root][i]=las[i]; |
| } | } | ||
| - | } s1,s2; | + | }s1,s2; |
| </code> | </code> | ||
| 行 288: | 行 285: | ||
| int la,lb; | int la,lb; | ||
| - | struct SQAM {//构建复杂度是n方的 | + | struct SQAM { |
| - | int ch[MAXL][MAXM],las[MAXM],pre[MAXL]; | + | int ch[MAXL][MAXM],las[MAXM]; |
| - | int root,tot; | + | int root; |
| void init() { | void init() { | ||
| - | root=tot=1; | + | root=1;//构造根节点 |
| - | for(int i=0; i<MAXM; i++) las[i]=1; //上一个是根节点 | + | |
| } | } | ||
| - | void insert(int c) { | + | void work(char s[]) { |
| - | int p=las[c],np=++tot;//p是上一个字符c出现的结点 np是现在结点 | + | int len=strlen(s); |
| - | pre[np]=p;//现在结点的前驱是上一个出现的结点 | + | for(int i=len-1;i>=0;i--) { |
| - | for(int i=0; i<MAXM; i++) { //对于每个字符对于字符c都要更新下一次出现的位置 | + | for(int j=0;j<MAXM;j++) ch[i+2][j]=las[j];//每个字符是一个节点 根节点是1 所以0位置字符状态为2 |
| - | for(int j=las[i]; j&&!ch[j][c]; j=pre[j]) { //这个位置没有接过c，这次接上 然后一直跳pre都更新 | + | las[s[i]-'a']=i+2; |
| - | ch[j][c]=np; | + | |
| - | } | + | |
| } | } | ||
| - | las[c]=np;//别忘了把最新的位置更新 | + | for(int i=0;i<MAXM;i++) ch[root][i]=las[i]; |
| } | } | ||
| - | } s1,s2; | + | }s1,s2; |
| struct Node { | struct Node { | ||
| 行 353: | 行 347: | ||
| for(int i=0; i<la; i++) { | for(int i=0; i<la; i++) { | ||
| S1.add(A[i]-'a'); | S1.add(A[i]-'a'); | ||
| - | s1.insert(A[i]-'a'); | ||
| } | } | ||
| + | s1.work(A); | ||
| for(int i=0; i<lb; i++) { | for(int i=0; i<lb; i++) { | ||
| S2.add(B[i]-'a'); | S2.add(B[i]-'a'); | ||
| - | s2.insert(B[i]-'a'); | ||
| } | } | ||
| + | s2.work(B); | ||
| int a1=BFS(1),a2=BFS(2),a3=BFS(3),a4=BFS(4); | int a1=BFS(1),a2=BFS(2),a3=BFS(3),a4=BFS(4); | ||
| printf("%d\n%d\n%d\n%d\n",a1,a2,a3,a4); | printf("%d\n%d\n%d\n%d\n",a1,a2,a3,a4); | ||
2020-2021/teams/legal_string/王智彪/序列自动机.1627814562.txt.gz · 最后更改: 2021/08/01 18:42 由 王智彪
