continue 题目 else break span strlen sta std
* 和? 的通配符问题
对应题目 FJUTOJ2579
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #include<queue>
- #include<vector>
- using namespace std;
- const int maxn=100050;
- const int maxsig=26;
- vector<int>vec[maxn];
- struct Aho
- {
- struct node
- {
- int next[maxsig];
- int fail;
- } stateTable[maxn];
- int cnt[maxn];
- int size,tcnt;
- queue<int>q;
- void init()
- {
- while(!q.empty())q.pop();
- memset(stateTable[0].next,0,sizeof(stateTable[0].next));
- vec[0].clear();
- size=1;
- tcnt=0;
- }
- int getid(char c)
- {
- return c-'a';
- }
- void insert(char *s)
- {
- int n=strlen(s);
- int now=0;
- init();
- for(int i=0;!i||s[i-1]; i++)
- {
- if(s[i]=='?'||s[i]==0)
- {
- if(now)
- {
- vec[now].push_back(i-1);
- now=0;
- tcnt++;
- }
- continue;
- }
- else
- {
- int c=getid(s[i]);
- if(!stateTable[now].next[c])
- {
- memset(stateTable[size].next,0,sizeof(stateTable[size].next));
- vec[size].clear();
- stateTable[now].next[c]=size++;
- }
- now=stateTable[now].next[c];
- }
- }
- }
- void build()
- {
- stateTable[0].fail=-1;
- q.push(0);
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- for(int i=0; i<maxsig; i++)
- if(stateTable[u].next[i])
- {
- int v=stateTable[u].fail;
- while(v!=-1)
- {
- if(stateTable[v].next[i])
- {
- stateTable[stateTable[u].next[i]].fail=stateTable[v].next[i];
- break;
- }
- v=stateTable[v].fail;
- }
- if(v==-1)stateTable[stateTable[u].next[i]].fail=0;
- q.push(stateTable[u].next[i]);
- int x=stateTable[u].next[i];
- if(vec[stateTable[x].fail].size())
- {
- vec[x].insert(vec[x].begin(),vec[stateTable[x].fail].begin(),vec[stateTable[x].fail].end());
- }
- }
- }
- }
- int match(char *s)
- {
- if(tcnt==0)return 0;
- int n=strlen(s);
- int now=0;
- for(int i=0; i<n; i++)
- {
- cnt[i]=0;
- int c=getid(s[i]);
- if(stateTable[now].next[c])
- now=stateTable[now].next[c];
- else
- {
- int v=stateTable[now].fail;
- while(v!=-1&&!stateTable[v].next[c])
- v=stateTable[v].fail;
- if(v==-1)now=0;
- else now=stateTable[v].next[c];
- }
- for(int j=0; j<vec[now].size(); j++)
- {
- if(i>=vec[now][j])
- {
- cnt[i-vec[now][j]]++;
- if(cnt[i-vec[now][j]]==tcnt) return i-vec[now][j];
- }
- }
- }
- return -1;
- }
- } aho;
- char s1[100010],s2[100010],tmp[100010];
- int solve(char *s1,char *s2)
- {
- int l1=strlen(s1),l2=strlen(s2);
- int tl=0;
- for(int i=0; i<l2; i++)if(s2[i]!='*')tl++;
- if(tl>l1)return 0;
- int s=-1;
- for(int i=0;i==0||s1[i-1]; i++)
- {
- if(s1[i]==s2[i]||(s1[i]!=0&&s2[i]=='?'))continue;
- if(s2[i]=='*')s=i+1;
- else return 0;
- break;
- }
- if(s==-1)return 1;
- for(int i=l1-1,j=l2-1;; i--,j--)
- {
- if(i==-1&&j==-1)break;
- if(i==-1)
- {
- if(s2[j]!='*')return 0;
- break;
- }
- if(j==-1)return 0;
- if(s1[i]==s2[j]||s2[j]=='?')
- {
- s1[l1=i]=s2[j]=0;
- }
- else if(s2[j]=='*')break;
- else return 0;
- }
- int ts=s-1;
- for(int i=1; i<l2-tl; i++)
- {
- if(s2[s]=='*')
- {
- s++;
- continue;
- }
- int len=0;
- for(; s2[s]!='*'&&s2[s]; s++)
- {
- tmp[len]=s2[s];
- tmp[++len]=0;
- }
- s++;
- aho.insert(tmp);
- aho.build();
- int pos=aho.match(s1+ts);
- if(pos==-1)return 0;
- else
- {
- ts+=pos+len;
- if(ts>l1)return 0;
- }
- }
- return 1;
- }
- int main()
- {
- while(~scanf("%s%s",s1,s2))
- {
- aho.init();
- if(solve(s1,s2))
- printf("YES\n");
- else printf("NO\n");
- }
- return 0;
- }
病毒侵袭 FJUTOJ2581
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #include<queue>
- #include<vector>
- using namespace std;
- vector<int>vs[1111];
- const int maxn=100050;
- const int maxsig=128;
- struct Aho
- {
- struct node
- {
- int next[maxsig];
- int fail,cnt;
- } stateTable[maxn];
- int size;
- queue<int>q;
- void init()
- {
- while(!q.empty())q.pop();
- memset(stateTable[0].next,0,sizeof(stateTable[0].next));
- stateTable[0].cnt=0;
- size=1;
- }
- int getid(char c)
- {
- return c;
- }
- void insert(char *s,int x)
- {
- int n=strlen(s);
- int now=0;
- for(int i=0; i<n; i++)
- {
- int c=getid(s[i]);
- if(!stateTable[now].next[c])
- {
- memset(stateTable[size].next,0,sizeof(stateTable[size].next));
- stateTable[size].cnt=0;
- stateTable[now].next[c]=size++;
- }
- now=stateTable[now].next[c];
- }
- stateTable[now].cnt=x;
- }
- void build()
- {
- stateTable[0].fail=-1;
- q.push(0);
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- for(int i=0; i<maxsig; i++)
- if(stateTable[u].next[i])
- {
- int v=stateTable[u].fail;
- while(v!=-1)
- {
- if(stateTable[v].next[i])
- {
- stateTable[stateTable[u].next[i]].fail=stateTable[v].next[i];
- break;
- }
- v=stateTable[v].fail;
- }
- if(v==-1)stateTable[stateTable[u].next[i]].fail=0;
- q.push(stateTable[u].next[i]);
- }
- }
- }
- void Get(int u,int i)
- {
- while(u!=-1)
- {
- if(stateTable[u].cnt)
- vs[i].push_back(stateTable[u].cnt);
- u=stateTable[u].fail;
- }
- }
- void match(char *s,int x)
- {
- int n=strlen(s);
- int now=0;
- for(int i=0; i<n; i++)
- {
- int c=getid(s[i]);
- if(stateTable[now].next[c])
- now=stateTable[now].next[c];
- else
- {
- int v=stateTable[now].fail;
- while(v!=-1&&!stateTable[v].next[c])
- v=stateTable[v].fail;
- if(v==-1)now=0;
- else now=stateTable[v].next[c];
- }
- if(stateTable[now].cnt)
- Get(now,x);
- else if(stateTable[now].fail)Get(stateTable[now].fail,x);
- }
- }
- } aho;
- char s[10010];
- int main()
- {
- int n;
- while(~scanf("%d",&n))
- {
- aho.init();
- for(int i=1; i<=n; i++)
- scanf("%s",s),aho.insert(s,i),vs[i].clear();
- aho.build();
- int m;
- scanf("%d",&m);
- for(int i=1; i<=m; i++)
- scanf("%s",s),aho.match(s,i);
- int ans=0;
- for(int i=1; i<=m; i++)
- {
- if(vs[i].size())
- {
- sort(vs[i].begin(),vs[i].end());
- vs[i].erase(unique(vs[i].begin(),vs[i].end()),vs[i].end());
- printf("web %d:",i);
- for(int j=0; j<vs[i].size(); j++)
- printf(" %d",vs[i][j]);
- printf("\n");
- ans++;
- }
- }
- printf("total: %d\n",ans);
- }
- return 0;
- }
病毒侵袭持续中 FJUTOJ2582
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #include<queue>
- #include<vector>
- using namespace std;
- const int maxn=100050;
- const int maxsig=128;
- struct Aho
- {
- struct node
- {
- int next[maxsig];
- int fail,cnt;
- } stateTable[maxn];
- int ans[10001];
- int size;
- queue<int>q;
- void init()
- {
- while(!q.empty())q.pop();
- memset(ans,0,sizeof(ans));
- memset(stateTable[0].next,0,sizeof(stateTable[0].next));
- stateTable[0].cnt=0;
- size=1;
- }
- int getid(char c)
- {
- return c;
- }
- void insert(char *s,int res)
- {
- int n=strlen(s);
- int now=0;
- for(int i=0; i<n; i++)
- {
- int c=getid(s[i]);
- if(!stateTable[now].next[c])
- {
- memset(stateTable[size].next,0,sizeof(stateTable[size].next));
- stateTable[size].cnt=0;
- stateTable[now].next[c]=size++;
- }
- now=stateTable[now].next[c];
- }
- stateTable[now].cnt=res;
- }
- void build()
- {
- stateTable[0].fail=-1;
- q.push(0);
- while(!q.empty())
- {
- int u=q.front();
- q.pop();
- for(int i=0; i<maxsig; i++)
- if(stateTable[u].next[i])
- {
- int v=stateTable[u].fail;
- while(v!=-1)
- {
- if(stateTable[v].next[i])
- {
- stateTable[stateTable[u].next[i]].fail=stateTable[v].next[i];
- break;
- }
- v=stateTable[v].fail;
- }
- if(v==-1)stateTable[stateTable[u].next[i]].fail=0;
- q.push(stateTable[u].next[i]);
- }
- }
- }
- void Get(int u)
- {
- int res=0;
- while(u!=-1)
- {
- if(stateTable[u].cnt)
- ans[stateTable[u].cnt]++;
- u=stateTable[u].fail;
- }
- }
- int match(char *s)
- {
- int n=strlen(s);
- int now=0;
- for(int i=0; i<n; i++)
- {
- int c=getid(s[i]);
- if(stateTable[now].next[c])
- now=stateTable[now].next[c];
- else
- {
- int v=stateTable[now].fail;
- while(v!=-1&&!stateTable[v].next[c])
- v=stateTable[v].fail;
- if(v==-1)now=0;
- else now=stateTable[v].next[c];
- }
- Get(now);
- }
- }
- }aho;
- char ss[1001][51];
- char s[2000001];
- int main()
- {
- int n;
- while(~scanf("%d",&n))
- {
- aho.init();
- for(int i=1;i<=n;i++)
- {
- scanf("%s",ss[i]);
- aho.insert(ss[i],i);
- }
- aho.build();
- scanf("%s",s);
- aho.match(s);
- for(int i=1;i<=n;i++)
- if(aho.ans[i])
- printf("%s: %d\n",ss[i],aho.ans[i]);
- }
- return 0;
- }
AC 自动机模板
来源: http://www.bubuko.com/infodetail-2250080.html