kmp算法入门,入门题集合

kmp算法入门,入门题集合

hd1711

Number Sequence

 

这篇排版有问题,不过试了几次都改不来也就这样吧

 

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 51840 Accepted Submission(s): 20751

 

Problem Description

Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M – 1] = b[M]. If there are more than one K exist, output the smallest one.

 

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].

 

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

 

Sample Input

 

2

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2

1 2 3 1 3

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1

 

Sample Output

6

-1

做题思路:给出一个主序列,和一个匹配序列,如果能够匹配,则输出匹配序列第一个数在主序列中的位置.

这道题是kmp的基础题.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000100], b[10004],NEXT[10010];
int t, x, y;
void getNETE() 
{
	int j=0,k=-1;
	NEXT[0] = -1;
	while(j<y-1)
	{
		if(k==-1 || b[j]==b[k])
		{
			j++;
			k++;
			NEXT[j] = k;
		}
		else	
		k = NEXT[k];
	}
}
void kmp()
{
	int i=0,j=0;
	while(i<x&&j<y)
	{
		if(j==-1 || a[i]==b[j]) 
		{
			i++;
			j++;
		} 
		else
		j = NEXT[j];
	}
	if(j==y)
		cout<<i-y+1<<endl;//返回下标
	else
		 cout<<-1<<endl;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&x,&y);
		for(int p=0;p<x;p++)
		{
			scanf("%d",&a[p]);
		}
		for(int p=0;p<y;p++)
		{	
			scanf("%d",&b[p]);
		}
		getNETE();
		kmp();
	}
	return 0;
}

 

开始输入啥都没问题,然后就是通不过,说什么时间超限,最后改过了改过去,才发现,用的是cin输入输出流,这个在算法竞赛那本紫书中也提到了,以后注意,然后尽量改掉用万能有文件的习惯,有的编译器,不支持。

 

Cyclic Nacklace
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7375    Accepted Submission(s): 3210

Problem Description
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. Being inspired by the entrepreneurial spirit of “HDU CakeMan”, he wants to sell some little things to make money. Of course, this is not an easy task.

As Christmas is around the corner, Boys are busy in choosing christmas presents to send to their girlfriends. It is believed that chain bracelet is a good choice. However, Things are not always so simple, as is known to everyone, girl’s fond of the colorful decoration to make bracelet appears vivid and lively, meanwhile they want to display their mature side as college students. after CC understands the girls demands, he intends to sell the chain bracelet called CharmBracelet. The CharmBracelet is made up with colorful pearls to show girls’ lively, and the most important thing is that it must be connected by a cyclic chain which means the color of pearls are cyclic connected from the left to right. And the cyclic count must be more than one. If you connect the leftmost pearl and the rightmost pearl of such chain, you can make a CharmBracelet. Just like the pictrue below, this CharmBracelet’s cycle is 9 and its cyclic count is 2:

Now CC has brought in some ordinary bracelet chains, he wants to buy minimum number of pearls to make CharmBracelets so that he can save more money. but when remaking the bracelet, he can only add color pearls to the left end and right end of the chain, that is to say, adding to the middle is forbidden.
CC is satisfied with his ideas and ask you for help.
 

Input
The first line of the input is a single integer T ( 0 < T <= 100 ) which means the number of test cases.
Each test case contains only one line describe the original ordinary chain to be remade. Each character in the string stands for one pearl and there are 26 kinds of pearls being described by ‘a’ ~’z’ characters. The length of the string Len: ( 3 <= Len <= 100000 ).
 

Output
For each case, you are required to output the minimum count of pearls added to make a CharmBracelet.
 

Sample Input
3 aaa abca abcde

 

Sample Output
0 2 5

[题目大意:求再加几个,才能构成循环] 

【题解】【kmp】

【kmp,利用失配函数,求出最小循环节(最小循环节=原串长度-末位失配),首先判断循环节是否为0,若为0,直接输出原串长度;然后看原串是否能被循环节整除,若能,则输出0,;若不能,则求出还有几位没有循环,输出】

 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100010;
char str[MAXN];
int _next[MAXN];

void getNext(char *p)
{
    int j,k;
    j=0;
    k=-1;
    int len=strlen(p);
    _next[0]=-1;
    while(j<len)
    {
        if(k==-1||p[j]==p[k])
        {
            j++;
            k++;
            _next[j]=k;
        }
        else k=_next[k];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",&str);
        getNext(str);
        int len=strlen(str);//str字符串的个数 
        if(_next[len]==0)// 判断循环节是否为0,若为0,直接输出原串长度;
        {
            printf("%d\n",len);
            continue;
        }
        int t=len-_next[len];
        if(len%t==0)//原串是否能被循环节整除
		printf("0\n");
        else
        {
            printf("%d\n",t-len%t);//几位没有循环
        }
    }
    return 0;
}

  
 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114892.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • QTabWidget样式表右侧_qt qwidget

    QTabWidget样式表右侧_qt qwidget1、QTabWidget模型,来自于网络:2、样式设置:this->setStyleSheet(“QTabWidget::pane{border-width:1px;border-color:rgb(48,104,151);\border-style:outset;background-color:rgb(132,171,208);\background:transparent;}\QTabW.

  • 微博第三方登陆请求授权出现错误码:21322(重定向地址不匹配)的解决方法

    微博第三方登陆请求授权出现错误码:21322(重定向地址不匹配)的解决方法

    2021年10月25日
  • 口罩、安全帽识别比赛踩坑记(一) 经验漫谈及随想

    口罩、安全帽识别比赛踩坑记(一) 经验漫谈及随想前言       因为疫情迎来的史无前例大假期,从开始理直气壮的天天划手机,到中间百无聊赖的躺尸,再到之后实在憋得慌,就想找点什么事搞一搞。恰好这时,一直关注的极视角联合Intel公司举办了一个对口罩和安全帽进行识别的比赛,能免费用一个月的云服务器对于我这还在用跑个Demo都能卡死的老爷机来说还是相当具有吸引力的。于是…

  • 黑石发展历程_从殖民地到美帝

    黑石发展历程_从殖民地到美帝黑石集团(BlackstoneGroup)是全球领先的另类资产管理和提供金融咨询服务的机构,在华尔街拥有举足轻重的地位。今天,我们分享一篇纵向整理黑石集团崛起的好文,梳理黑石帝国的发展史。黑石集团于1985年成立于纽约,专注旅游、酒店、化工、汽车、国防、消费品以及医药等领域

  • 多线程C语言_多线程c++

    多线程C语言_多线程c++C程序中一直同时执行多项任务。例如c多线程控制控件实例,一个程序也许:(1)在执行程序过程中借助完成并行任务来提升性能。(2)在处理用户输入的同时,在后台进行耗时的数据通信和即时操作。通过并行执行(concurrentexecution)程序中的个别代码,可以推动不同任务同时进行。特别是在多处理器系统(当然也包含多核处理器)上,程序通过并行制度更有效地使用平台资源,其意义越来越重大。C1…

  • python 如何使用swagger

    swagger介绍swagger是一个api文档工具,集api管理,测试,访问于一体的网页版api文档工具了解更多,请访问相关网站swagger官网swaggergithubOpenApi参数说明python相关包connexionflasggerflask-swag,flask-swaggerFlask-RESTPluspythonswagger-cod…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号