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)


相关推荐

  • Element-UI + Vue,孙鑫Java视频教程百度网盘

    Element-UI + Vue,孙鑫Java视频教程百度网盘},},}[]()分页功能的实现==========================================================================mysql分页查询:SELECTid,name,bir,sex,addressFROMt_userLIMIT#{start},#{rows}后端控制器:@RestController@RequestMapping(“/user”)..

  • Oracle 创建表空间

    Oracle 创建表空间–删除表空间droptablespacenacosincludingcontentsanddatafiles—-创建表空间并定义路径createtablespacenacos–表空间名datafile’D:/app/Administrator/oradata/nacos/nacos.dbf’size500m–大小初始值autoextendon–自动扩展next50mmaxsize20480m–每次扩展50m,最大为20480mex…

  • 如何打开sln文件并显示窗口_在.sln文件中设置Visual Studio默认启动项目的简单方法…[通俗易懂]

    如何打开sln文件并显示窗口_在.sln文件中设置Visual Studio默认启动项目的简单方法…[通俗易懂]昨天在一台电脑上用git新签出一个项目进行build,却出现一堆编译错误,而在原先的开发机上build无任何错误。对比分析后发现,开发机上VS的启动项目(startupproject)与这台电脑上的不一样,改为一样后,build立马成功。看来问题与msbuild编译VS项目的顺序有关,而哪个项目作为启动项目会影响到这个编译顺序。要避免这个问题,就要保证git签出的VS解决方案的启动项目是一致的,…

  • 怎样更改pycharm的项目默认保存路径_vscode怎么给python导入包

    怎样更改pycharm的项目默认保存路径_vscode怎么给python导入包 参考原文:https://blog.csdn.net/yggaoeecs/article/details/78378938  还有这篇,同时讲了anaconda的安装:https://blog.csdn.net/qq_29883591/article/details/78077244https://blog.csdn.net/qq_29883591/article/details/78…

  • 串口通信的三种方式(查询、中断、DMA)

    串口通信的三种方式(查询、中断、DMA)

  • 单点登录sso的实现原理(单点登录原理)

    什么是单点登录一个账户在多个系统上实现单一用户的登录为什么用单点登录单点登录可以做到在不记录用户密码的情况下,实现不同系统之间的资源共享,自动登录不安全,单点登录,一处登录,处处都可用,不用做多余的登录操作引用一个很经典的案例比如现在有OA系统、门户系统、人力资源管理系统、档案管理系统、生产管理系统、xx系统等,这么多个系统在一个公司里面,如果一个用户需要使用这么多个系统,那每天都要登录…

发表回复

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

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