KMP及AC自动机_芜~湖的博客-程序员秘密

技术标签: 算法KMP  AC自动机  

题目链接:HDU 1711
KMP模板题。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1e6+10;
int a[maxn],b[maxn],Next[maxn];
int n,m;
void GetNext() {
    int i=0,j=-1;
    Next[0]=-1;
    while(i<m-1) {
        if(j==-1||b[i]==b[j]) {
            j++;
            i++;
            Next[i]=j;
        } else
            j=Next[j];
    }
}
int KMP() {
    GetNext();
    int i=0,j=0;
    while(i<n&&j<m) {
        if(j==-1||a[i]==b[j]) {
            i++;
            j++;
        } else
            j=Next[j];
    }
    if(j==m)
        return i-j+1;
    return -1;
}
int main() {
    int t;
    while(cin>>t) {

        while(t--) {
            cin>>n>>m;
            mem(Next,0);
            for(int i=0; i<n; i++)
                cin>>a[i];
            for(int j=0; j<m; j++)
                cin>>b[j];
            cout<<KMP()<<endl;
        }
    }
    return 0;
}

Power Strings

题目链接:POJ 2406

题目是问,在一个字符串S中,最多有几个相同的子串连接而成。例如:字符串ababab,它最多是由3个子串ab连接而成。
此题主要使用KMP算法的定义。
对于一个长度为len的字符串S,若Next[len]=k,则S[0 ~ k-1]==S[len-k ~ len-1]。k是字符串S前缀后缀的最大匹配长度。当len-next[len]是len的约数时,则S[0 ~ (len-Next[len]-1)]一定是字符串S的最大重复字串,长度为len-Next[len],并且循环次数为 len/(len-Next[len])。
例如:字符串S:ababab
 

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS() std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
const int maxn=1e6+10;
using namespace std;
string str1;
int Next[maxn];
void GetNext()
{
	mem(Next,0);
	Next[0]=-1;
	int j=0,k=-1;
	int len=str1.size();
	while(j<len)  //需要求出Next[len],使用j<len
	{
		if(k==-1||str1[j]==str1[k])
		{
			j++;
			k++;
			if(str1[j]!=str1[k])
				Next[j]=k;
			else
				Next[j]=Next[k];
		}
		else
		{
			k=Next[k];
		}
	}
}
int main()
{
	IOS();
	while(cin>>str1)
	{
		if(str1==".")
			break;
		GetNext();
		int len=str1.size();
		if(len%(len-Next[len])==0)
			cout<<len/(len-Next[len])<<endl;
		else
			cout<<1<<endl;
	}
	return 0;
}

CodeForces 25E

Test 

Sometimes it is hard to prepare tests for programming problems. Now Bob is preparing tests to new problem about strings — input data to his problem is one string. Bob has 3 wrong solutions to this problem. The first gives the wrong answer if the input data contains the substring s1, the second enters an infinite loop if the input data contains the substring s2, and the third requires too much memory if the input data contains the substring s3. Bob wants these solutions to fail single test. What is the minimal length of test, which couldn't be passed by all three Bob's solutions?

Input

There are several test cases. For each test case there are exactly 3 lines. The i-th line contains string si. All the strings are non-empty, consists of lowercase Latin letters, the length of each string doesn't exceed 105.

Output

For each test case output one number — what is minimal length of the string, containing s1, s2 and s3 as substrings.

Example

Input:
ab
bc
cd
abacaba
abaaba
x

Output:
4
11

题意:给定三个字符串,组成一个新的字符串,使新的字符串的子串包含给定的三个字符串,新的字符串最短为多少。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS() std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
const int maxn=1e6+10;
using namespace std;
string str1;
int Next[maxn];
void GetNext()
{
	mem(Next,0);
	Next[0]=-1;
	int j=0,k=-1;
	int len=str1.size();
	while(j<len)  //需要求出Next[len],使用j<len
	{
		if(k==-1||str1[j]==str1[k])
		{
			j++;
			k++;
			if(str1[j]!=str1[k])
				Next[j]=k;
			else
				Next[j]=Next[k];
		}
		else
		{
			k=Next[k];
		}
	}
}
int main()
{
	IOS();
	while(cin>>str1)
	{
		if(str1==".")
			break;
		GetNext();
		int len=str1.size();
		if(len%(len-Next[len])==0)
			cout<<len/(len-Next[len])<<endl;
		else
			cout<<1<<endl;
	}
	return 0;
}

题目链接:HDU2222

Keywords Search

AC自动机模板题

建树(详解看代码注释):

void insertWords(string s){
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++cnt;
        root = trie[root][next];
    }
    cntword[root]++;      //当前节点单词数+1
}

GetFail数组:(都说类似KMP,把线性递归改成了bfs(详解看代码注释))

void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
//fail[now]    ->当前节点now的失败指针指向的地方
//tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0;i<26;i++){      //查询26个字母
            if(trie[now][i]){
                //如果有这个子节点为字母i+'a',则
//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
                //有点绕,为了方便理解特意加了括号

                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else//否则就让当前节点的这个子节点
                //指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
        }
    }
}

query函数(详解看代码注释):

int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){    //遍历文本串
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){
            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
            ans += cntword[j];
            cntword[j] = -1;    //将遍历国后的节点标记,防止重复计算
        }
    }
    return ans;
}

完整代码:

#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn =  500005;
int trie[maxn][26]; //字典树
int cntword[maxn];  //记录该单词出现次数
int fail[maxn];     //失败时的回溯指针
int cnt = 0;
char s[55];
char str[1000005];
void insertWords(string s){
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++cnt;
        root = trie[root][next];
    }
    cntword[root]++;      //当前节点单词数+1
}
void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
//fail[now]    ->当前节点now的失败指针指向的地方
//tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0;i<26;i++){      //查询26个字母
            if(trie[now][i]){
                //如果有这个子节点为字母i+'a',则
//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
                //有点绕,为了方便理解特意加了括号

                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else//否则就让当前节点的这个子节点
                //指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
        }
    }
}
int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){    //遍历文本串
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){
            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
            ans += cntword[j];
            cntword[j] = -1;    //将遍历国后的节点标记,防止重复计算
        }
    }
    return ans;
}

int main() {
	int t;
	scanf("%d", &t);
	while(t--)
	{
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
       scanf("%s", s);
        insertWords(s);
    }
    fail[0] = 0;
    getFail();
    scanf("%s", str);
    cout << query(str) << endl;
    //初始化 
    mem(trie,0);
    mem(cntword,0);
    mem(fail,0);
    }
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/X_X_X_666/article/details/119804796

智能推荐

微信群如何实现只接收红包消息提醒_wangchensong的博客-程序员秘密_微信群红包提醒

有些时候有些群,我们只关心群里的红包信息,并不关心其他消息.那么我们怎么实现.今天交大家一个小妙招.下载"微消息提醒" app.应用商店可以下载,绿色图标那个.然后使用他的"群消息屏蔽功能".采用方式一,填写群名称,在允许列表里填写一个群里不存在的好友昵称,这样就可以实现群消息只提醒红包了.非常的方便....

设计模式--模板方法模式Template method(类行为型)_benbenxiongyuan的博客-程序员秘密

1.概述在面向对象开发过程中,通常我们会遇到这样的一个问题:我们知道一个算法所需的关键步骤,并确定了这些步骤的执行顺序。但是某些步骤的具体实现是未知的,或者说某些步骤的实现与具体的环境相关。例子1:银行业务办理流程在银行办理业务时,一般都包含几个基本固定步骤:取号排队->办理具体业务->对银行工作人员进行评分。取号取号排队和对银行工作人员进行评分业务逻辑是一样的。但是办

确定进制_yanyanwenmeng的博客-程序员秘密

 描述6 * 9 = 42 对于十进制来说是错误的,但是对于13进制来说是正确的。即, 6(13)* 9(13)= 42(13), 而 42(13)= 4 * 131+ 2 * 130= 54(10)。你的任务是写一段程序,读入三个整数p、q和 r,然后确定一个进制 B(2&amp;lt;=B&amp;lt;=16) 使得 p * q = r。 如果 B 有很多选择, 输出最小的一个。例如:p =...

Java 获取 CPU 核数_allway2的博客-程序员秘密_java获取cpu核数

概述一个系统可能包含多个物理 CPU(中央处理单元),也可以包含一个或多个内核(处理器)。另外,每个核心可以有多个线程,通常2(超-线程技术从英特尔CPU)。示例:具有 2 个双核 CPU 的系统。2 个 CPU x 每个 CPU 2 个内核 =总共 4 个内核您可以确定的数量内核采用静态方法,提供给Java虚拟机availableProcessors从类运行。此方法从 Java 1.4 开始可用。每个 Java 应用程序都有一个Runtime类的单个实例,它允许应用程序与应...

matlab icol,人脸识别-2dpca之Matlab程序_maruShien的博客-程序员秘密

本程序采用2级PCA提取特征,最小藕欧距离分类器进行人脸识别,实验数据为orl人脸库。本文作为我从事模式识别研究的开始,留下此代码作为见证。由于Matlab软件是初次使用,很多函数还不是很熟识,所以代码的执行效率可能不够高,本代码仅供参考。参考文献:J. Yang, D. Zhang, A.F. Frangi, J.Y.Yang, Two-dimensional PCA: a new approa...

出走的门徒之四:丰元创投朱会灿:冒险的牧师_chengtongjia6378的博客-程序员秘密

风口不会随便眷顾一个人。因为历史不会对默默“打怪升级”着墨,它只看结果。 在阿西莫夫的代表作《基地》中,除了先知谢顿贯穿全线,其他主角都是门徒。他们内在为直觉所驱动,外在被时代所推动。他们在历史上的出场毫无征兆,却在潮流中游刃有余。你会惊叹,为什么是他? ...

随便推点

windows10 keras下的yolov3实现之报错处理方法_Keith_Kobura的博客-程序员秘密

Yolov3是目前是目标检测中检测速度最快的算法之一,前作v1和v2版本版本虽然检测速度快,但是对小物体的识别不擅长,精度方面不及RCNN系列,而v3得横空出世,改进了很多问题,在精度和速度方面得到了很好的统一。关于yolov3可以参考以下博文yolo系列之yolo v3【深度解析】本文参考以下博文windows10+keras下的yolov3的快速使用及自己数据集的训练,实现了w...

DB2TCP_CLIENT_RCVTIMEOUT 的作用_匿_名_用_户的博客-程序员秘密

本文主要讲述DB2客户端配置参数 DB2TCP_CLIENT_RCVTIMEOUT的作用解释:DB2TCP_CLIENT_RCVTIMEOUT - Adjust this variable on the client to terminate the connection if data is not received from the server within a specif

Arduino运行Linux系统,Arduino IDE ESP8266环境搭建 for Liunx_飞行电熨斗的博客-程序员秘密

Arduino IDE 安装下载Arduino IDE选择Linux64 bits(根据自己的系统选择)(保存路径随意,我保存在/opt/arduino/)下载完毕后切入arduino目录,并执行安装脚本cd/opt/arduinosudoinstall.sh安装ESP8266开发板创建 esp8266com目录cd/opt/arduino/hardwaresudomkdiresp8...

在fedora 20中安装VM Tools 出现以下错误,解决方法_centos-com的博客-程序员秘密

在fedora 20中安装VM Tools 出现以下错误,,求解,最好给出详细的命令2014-03-14 20:45fly夜夜飞|分类:Linux| 浏览657次[[email protected] vmware-tools-distrib]# ./vmware-install.pl The installer found the following conflicting packag

C数据结构2.1-线性表抽象数据类型_ai516001066的博客-程序员秘密

定义:零个或多个数据元素的有限序列特点:它是一个序列。数据元素之间是有序的。数据元素是一对一的关系有限性。线性表中数据元素的个数是有限的。零个元素的有限序列被称为空表线性表的常见操作:(增删改查)创建和初始化(排队),查找(寻找),插入,删除,清空ADT 线性表(SequenceList)Data  1.线性表的数据元素是一个集合{a_1,...

2019腾讯校招实习笔试题打怪兽_wwxy261的博客-程序员秘密

小Q打算穿越怪兽谷,他不会打怪,但是他有钱。他知道,只要给怪兽一定的金币,怪兽就会一直护送着他出谷。在谷中,他会依次遇见N只怪兽,每只怪兽都有自己的武力值和要“贿赂”它所需的金币数。如果小Q没有“贿赂”某只怪兽,而这只怪兽“武力值”又大于护送他的怪兽武力之和,这只怪兽就会攻击他。小Q想知道,要想成功穿越怪兽谷而不被攻击,他最少要准备多少金币。输入格式第一行包含整数N,表示怪...

推荐文章

热门文章

相关标签