首页 > 其他 > 详细

Subsequence(序列自动机模板题)

时间:2019-04-20 22:26:29      阅读:136      评论:0      收藏:0      [点我收藏+]

 题目链接:https://nanti.jisuanke.com/t/38232

题目大意:给你一个字符串,然后再给你m个字符串,然后问你在第一个字符串中不连续的子串能不能构成输入的子串。

具体思路:构建一个序列自动机就可以了。刚接触,记录下

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn =2e5+100;
 6 const int mod = 1e9+7;
 7 char str[maxn];
 8 int now[30];
 9 int nex[maxn][30];
10 void init()
11 {
12     memset(now,-1,sizeof(now));
13     int len=strlen(str);
14     for(int i=len-1; i>=0; i--)
15     {
16         for(int j=0; j<26; j++)
17         {
18             nex[i][j]=now[j];
19         }
20         now[str[i]-a]=i;
21     }
22 }
23 int main()
24 {
25     scanf("%s",str);
26     init();
27     int m;
28     scanf("%d",&m);
29     while(m--)
30     {
31         scanf("%s",str);
32         int len=strlen(str);
33         int pos=now[str[0]-a];
34         int flag=1;
35         if(pos==-1)
36             flag=0;
37         for(int i=1; i<len; i++)
38         {
39             pos=nex[pos][str[i]-a];
40             if(pos==-1)
41             {
42                 flag=0;
43                 break;
44             }
45         }
46         if(!flag)
47             printf("NO\n");
48         else
49             printf("YES\n");
50     }
51     return 0;
52 }

 

Subsequence(序列自动机模板题)

原文:https://www.cnblogs.com/letlifestop/p/10742856.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!