dutacm.club_1087_Common Substrings_(KMP)_(结合此题通俗理解kmp的next数组)
2024-09-30 18:08:12
1087: Common Substrings
Time Limit:3000/1000 MS (Java/Others) Memory Limit:163840/131072 KB (Java/Others)
Total Submissions:849 Accepted:108
Total Submissions:849 Accepted:108
Description
You are given two long strings A and B. They are comprised of lowercase letters. You should compute how many suffixes of A are the prefixes of B.
Input
In the first line is a number T (0<T≤100) , indicating the cases following.
In the next T lines each line contains two strings — A and B.
( 0<|A|≤10^5,0<|B|≤10^5)
Output
There should be exactly T lines.
Each line contain a number — the answer.
Sample Input
1
abcc ccba
Sample Output
2
HINT
In the first case, cc and c are two of the suffixes of string A, and they are the prefixes of string B.
题意:给两个字符串A和B,问A的所有后缀中,有多少个是B的前缀。
一看也是没思路啊。。。题解用的KMP,让我有点懵逼,仔细一想,让我更加理解之前学的kmp。
思路:利用kmp算法中求的next数组的过程即可得到答案,因为next的数组实质是:next[i]表示str[1--i]这个子串的前缀和后缀的最大公共长度(这里的前缀和后缀是之前看的kmp的博文中的定义,与普通的有细微差异)。
kmp算法利用这个数组,在失配时可以更加快地往后搜索(而不是从字符串的下一个字符开始重新与模式串的第一个字符开始匹配),next[i]的值即为模式串的第i+1个字符失配时将模式串向右移动至next[i]为当前要匹配的字符。因为模式串mo[i-next[i]+1,i](这是个后缀)这个子串与mo[1,next[i]](这是一个前缀)这个子串是一样的,所以将模式串右移至这个前缀代替这个后缀的位置,这样就达到了更加高效匹配的目的。结合博文看容易理解。。。
好题啊好题!!!!!!
#include <cstdio>
#include <cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
#define N 100005
#define LL long long char A[N],B[N],T[N<<];
int Next[N<<],lena,lenb,lent; void getNext()
{
int p=;
memset(Next,,sizeof(Next));
for(int i=;i<lent;i++)
{
while(p>&&T[p+]!=T[i])
p=Next[p];
if(T[p+]==T[i])
p++;
Next[i]=p;
}
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",A,B);
lena=strlen(A);
lenb=strlen(B);
strcpy(T+,B);
T[lenb+]='#';
strcpy(T+lenb+,A);
T[lena+lenb+]='\0';
//cout<<T+1<<endl;
lent=lena+lenb+;
getNext();
//for(int i=1;i<lent;i++)
// cout<<Next[i]<<' ';
//cout<<endl;
int tmp=lent-,res=;
while(tmp!=)
{
if(Next[tmp]>)
res++;
tmp=Next[tmp];
}
printf("%d\n",res);
}
return ;
}
最新文章
- oracle 关于null值排序
- HDU 4454 Stealing a Cake(枚举角度)
- cocos2d-x-3.11.1 初使用
- PHP强大的内置filter (二) 完
- 【转载】TalkingData首席金融行业专家鲍忠铁:18亿数据解读移动互联网
- 【风马一族_Android】Android Studio 给APP设置签名
- android中利用实现二级联动的效果
- C++学习(五)
- Volley的三种基本用法StringRequest的Get和post用法以及JsonObjectRequest
- Swift - 浮点数转换成整数(四舍五入与直接截断)
- VR的发展历程-VR全景智慧城市
- 【译】MongoDb vs Mysql—以NodeJs为例
- jenkins忘记管理员密码之解决方案
- es6 super关键字
- SQL 资源整理
- JxBrowser之二:常用函数addLoadListener
- tcpcopy用法
- 最小生成树问题(prim算法)POJ-1258 Agri-Net
- linux下配置tomcat集群的负载均衡
- Oracle XQuery 过滤XML查询SQL
热门文章
- 笔记本能连上WIFI网络,但是无法上网怎么办
- webpack—入门
- (源代码分析)Android-Universal-Image-Loader (图片异步载入缓存库)的使用配置
- Kafka跨集群同步工具——MirrorMaker
- HDU 5402 Travelling Salesman Problem (构造)(好题)
- android 特殊符号开头的联系人归并至“#”下
- 在对象内部尽量直接訪问实例变量 --Effictive Objective-C 抄书
- SSH-struts2的异常处理
- 开发,从需求出发 &;#183; 之二 造飞机的工厂
- python 时区