注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

bjfu-1023 双串匹配  

2012-12-19 17:49:47|  分类: ACM-bjfu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

双串匹配

时间限制(普通/Java):1000MS/3000MS          运行内存限制:16384KByte
总提交:52            测试通过:8

描述

串的模式匹配算法是计算机中应用最为广泛的算法之一。一般的模式匹配只有一个主串和一个子串,但是有的时候我们需要另一种特殊的匹配,暂称之为双串匹配。在这种应用中,有两个主串,一个子串,而且主串的长度和内容不一定一样,要求在两个主串的对应位置同时查找与目标子串相同的子串。比如下例:

主串1:Gather ye rosebuds while ye may,old time is still a-flying.

主串2:This same flower that smiles today, tomorrow will be dying.

子串: ing

匹配成功,结果为56,因为从两个主串的第56位字符开始,同时出现ing子串(出现'i')。

输入

输入首先包含一个正整数T(0<T<40),表示测试数据组数。

接下来T组测试数据,每组测试数据包含三个字符串,含义如上。其中两个主串长度均不超过1000000,子串长度不超过1000。

输出

对每组测试数据,如果匹配成功,请输出子串第一个字符在两个主串中首次同时出现的位置;如果匹配失败,则输出0,每组输出占一行。

样例输入

2
Gather ye rosebuds while ye may,old time is still a-flying.
This same flower that smiles today, tomorrow will be dying.
ing
ACACACACAC
ACMACMACM
CM

样例输出

56
0

————————————————————————————————————————

KMP简单应用。KMP的题做的比较少,这题直接打的模板

/*
* test1.cpp
*
* Created on: 2012-12-19
* Author: fudq
*/
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define N_PAR 1010//模式串,题目中的字串
#define N_TXT 1000010
char pattern[N_PAR],text1[N_TXT],text2[N_TXT];
int next[N_PAR],nextval[N_PAR],parlen,txtlen;

void get_nextval()
{
int i=0,j=-1;
nextval[0]=-1;
while(i<parlen)
{
if(j<0 || pattern[i]==pattern[j])
{
i++;j++;
if(pattern[i]!=pattern[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}

int kmp()
{
int i,j,a,b,pos;
a=(int)strlen(text1);
b=(int)strlen(text2);
txtlen=a<b?a:b;
parlen=(int)strlen(pattern);
get_nextval();
//从字串和主串相同的第一个开始
pos=0;
while(text1[pos]!=text2[pos])
{
pos++;
if(pos==txtlen)
return -1;
}
i=pos;j=0;
while(i<txtlen && j<parlen)
{
if(j<0 || (text1[i]==pattern[j] && text2[i]==pattern[j]))
{
i++;
j++;
}
else
j=nextval[j];
}
if(j==parlen)
return i-j;
else
return -1;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int T;
scanf("%d",&T);
getchar();
while(T--)
{
gets(text1);
gets(text2);
gets(pattern);
printf("%d\n",kmp()+1);
}
return 0;
}


  评论这张
 
阅读(76)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018