首页 > 代码库 > Problem F: 小金廷的逆袭
Problem F: 小金廷的逆袭
分析：这道题主要是考我们关于KMP算法的应用的！题目要求求出两个字符串中最长的连续字符的个数！由于题目的上限很大，所以暴力搜索的话肯定是会超时的！
题解：这个，选第一个字符串为目标，使用两个for循环来依次枚举所选的这个字符串的子字符串，然后求出该字符串的next[]数组，然后使用kmp算法，和第二个字符串对比匹配，由于题目要求的是连续的最长的子字符串，所以在枚举时一旦发现不能匹配上，就直接跳出内循环，然后再从外循环重新开始枚举并搜索！
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
int n,m,num;
while(scanf("%d%d",&n,&m)!=EOF)
{
while(m--)
{
getchar();
char a[20];
scanf("%s",a);
if(!strcmp(a,">>"))
{
scanf("%d",&num);
n=n>>num;
printf("%d\n",n);
}
if(!strcmp(a,"<<"))
{
scanf("%d",&num);
n=n<<num;
printf("%d\n",n);
}
if(!strcmp(a,"~"))
{
n=(~n);
printf("%d\n",n);
}
if(!strcmp(a,"|"))
{
scanf("%d",&num);
n=(n|num);
printf("%d\n",n);
}
if(!strcmp(a,"&"))
{
scanf("%d",&num);
n=(n&num);
printf("%d\n",n);
}
if(!strcmp(a,"^"))
{
scanf("%d",&num);
n=(n^num);
printf("%d\n",n);
}
}
}
return 0;
}
Description
小金廷酷爱数学，立志成为数学大神的他，最近想出了一个奇怪的东西-数字相似度。他相信数字之间必然存在着某种联系（或许像DNA一样），他定义数字之间的相似度为其最长的连续相同数字的长度。现在为了寻得更多的相似度，以便他更好的分析其中所存在的联系，他想请你帮他计算出一些相似度。
Input
输入包含多组测试数据。
每组测试数据包含1行，包含2个数n,m ( 0 < = m,n < = 10^1000 )
Output
输出仅包含一行，代表数字间的相似度。
Sample Input
Sample Output
Problem F: 小金廷的逆袭