HDU - 3407 - String-Matching Automata
先上题目:
String-Matching Automata
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 215 Accepted Submission(s): 140
Σ is the input alphabet (a finite nonempty set of symbols).
S is a finite nonempty set of states.
s0 is an element in S designated as the initial state.
δ is a function δ: S × Σ → S known as the transition function.
F is a (possibly empty) subset of S whose elements are designated as the final states.
An FSA with the above description operates as follows:
At the beginning, the automaton starts in the initial state s0.
The automaton continuously reads symbols from its input, one symbol at a time, and transits between states according to the transition function δ. To be specific, let s be the current state and w the symbol just read, the automaton moves to the state given by δ(s, w).
When the automaton reaches the end of the input, if the current state belongs to F, the string consisting sequentially of the symbols read by the automaton is declared accepted, otherwise it is declared rejected.
Just as the name implies, a string-matching automaton is a FSA that is used for string matching and is very efficient: they examine each character exactly once, taking constant time per text character. The matching time used (after the automaton is built) is therefore Θ(n). However, the time to build the automaton can be large.
Precisely, there is a string-matching automaton for every pattern P that you search for in a given text string T. For a given pattern of length m, the corresponding automaton has (m + 1) states {q0, q1, …, qm}: q0 is the start state, qm is the only final state, and for each i in {0, 1, …, m}, if the automaton reaches state qi, it means the length of the longest prefix of P that is also a suffix of the input string is i. When we reaches state qm, it means P is a suffix of the currently input string, which suggest we find an occurrence of P.
The following graph shows a string-matching automaton for the pattern “ababaca”, and illustrates how the automaton works given an input string “abababacaba”.
Apparently, the matching process using string-matching automata is quite simple (also efficient). However, building the automaton efficiently seems to be tough, and that’s your task in this problem.
0
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 10002
using namespace std; struct Trie{
int next[MAX][],fail[MAX],end[MAX],num[MAX][];
int root,L; int newnode(){
for(int i=;i<;i++){ next[L][i]=-; num[L][i]=;}
end[L++]=;
return L-;
}
void init(){
L=; root=newnode();
} void insert(char buf[]){
int len=strlen(buf);
int now = root;
for(int i=;i<len;i++){
if(next[now][buf[i]-'a']==-){
next[now][buf[i]-'a']=newnode(); }
now=next[now][buf[i]-'a'];
}
end[now]++;
} void build(){
queue<int> Q;
fail[root]=root;
for(int i=;i<;i++){
if(next[root][i]==-) next[root][i]=root;
else{
fail[next[root][i]]=root;
Q.push(next[root][i]);
}
}
while(!Q.empty()){
int now=Q.front();
Q.pop();
for(int i=;i<;i++){
if(next[now][i]==-) next[now][i]=next[fail[now]][i];
else{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
} void print(char buf[]){
int len=strlen(buf);
int now=root;
for(int i=;i<=len;i++){
printf("%d",i);
for(int j=;j<;j++) printf(" %d",next[now][j]);
printf("\n");
now=next[now][buf[i]-'a'];
}
}
}; Trie ac;
char s[MAX]; int main()
{
//freopen("data.txt","r",stdin);
while(scanf("%s",s),strcmp(s,"")){
ac.init();
ac.insert(s);
ac.build();
ac.print(s);//printf("\n");
}
return ;
}
/*3407*/
最新文章
- linux下配置ip地址四种方法(图文方法)
- Linux下Bash入门学习笔记
- 15分钟学会使用Git和远程代码库
- H3C Series Router MSR26-00与F3736 VPN IP SEC
- oracle ebs request一直pending
- flask中文问题
- Oracle客户端安装及配置
- axel源码学习(1)&mdash;&mdash;重要流程细节
- POJ1699Best Sequence(DFS)
- 如何让Windows程序只运行一个程序实例?
- Asp.net mvc中Controller的返回值
- 使用委托解决";线程间操作无效: 从不是创建控件“textBox1”的线程访问它"; 问题
- *循环-01. 求整数段和【help】
- ORA-12514:TNS:lisntener does not currently know of service requested in connect descriptor
- 怎样做ie兼容性
- C#中struct和class的区别详解
- angular url 传参
- sql server对已创建的表增加属性(自动增序)
- smartgit的安装
- [小知识] 关闭我的电脑里面的百度网盘以及修改win+e快捷键打开我的电脑