松岗怎么做企业网站设计,网站开发短期培训,做网站流量钱谁给,seo网站排名查询const int maxn 1000005;//定义所需要最大长度
struct Aho{struct state{int next[26];//trie树结构int fail,cnt;//失配指针和表示当前点作为结束点的标记}st[maxn];int size;//定义当前一共有多少个点queueintq;//层序遍历序列void init(){for(int i0;imaxn;i){…
const int maxn 1000005;//定义所需要最大长度
struct Aho{struct state{int next[26];//trie树结构int fail,cnt;//失配指针和表示当前点作为结束点的标记}st[maxn];int size;//定义当前一共有多少个点queueintq;//层序遍历序列void init(){for(int i0;imaxn;i){memset(st.next,0,sizeof(st.next));//初始化st[i].cntst[i].fail0;}size1;while(!q.empty())q.pop();}//插入函数 插入一个S串void Insert(char *s){int now0;int len strlen(s);for(int i0;ilen;i){if(!st[now].next[s[i]-a])st[now].next[s[i]-a]size;//如果没有这个点 就新作一个点 并让sizenow st[now].next[s[i]-a];//如果有 那么让当前指向继续走}st[now].cnt;//插入一个元素 当前位置下标记为一个串的结束}void build(){//构建失配指针q.push(0);//从根节点开始走 st[0].fail-1;//根节点失配指向-1while(!q.empty()){int u q.front();q.pop();for(int i0;i26;i){if(st[u].next[i]){//如果当前点的next[i]有字符 if(u0)st[st[u].next[i]].fail0; //如果当前点是根 就让其孩子指向自己else{//非根int v st[u].fail;//v存储的是当前点的失配指向while(v!-1){//如果v非-1 表示当前点非根节点if(st[v].next[i]){//父节点的失配位置也存在当前字符 那么对于父节点的孩子 失配指针直接指向父节点失配位置的相同字符next[i]的位置 对于u的next[i]来说 u的fail结点就是最长可能的位置 st[st[u].next[i]].failst[v].next[i];//指向父节点的失配结点的位置 fail 处的next[i] break;//已找到 跳出 } v st[v].fail;//如果没有这种结点 那么继续找 从非最长公共前缀串中找 }if(v-1)st[st[u].next[i]].fail0;//如果此时回到了根节点 就让他直接指向0 }q.push(st[u].next[i]); //将此点入队 层序遍历 }}} }int get(int u){int res 0;while(u!-1){resst[u].cnt;st[u].cnt0;//在找到she串后只能算一次 算过一次后就要清0 u st[u].fail;}}//查询s串中有多少个模板串int query(char *s){int len strlen(s);int res0,now 0;//now记录当前节点的位置for(int i0;ilen;i){//从匹配串的第一个字符开始 向后遍历 //找到now该指向的下标 if(st[now].next[s[i]-a])now st[now].next[s[i]-a];//如果当前位置下存在这个字符 就让now指向这里 else{//没有的话就不停找失配 int v st[now].fail;while(v!-1st[v].next[s[i]-a]0)v st[v].fail;//没有到根 并且这里没有当前字符 就不停找公共前缀串 if(v-1)now0;//如果最后没有返回根节点 else now st[v].next[s[i]-a]; //如果有 那么就让now指向那里 }if(st[now].cnt)resget(now); }return res;}
}aho;
