string matching(拓展KMP)
2024-08-31 10:59:23
Problem Description
String matching is a common type of problem in computer science. One string matching problem is as following:
Given a string s[0…len−1], please calculate the length of the longest common prefix of s[i…len−1] and s[0…len−1] for each i>0.
I believe everyone can do it by brute force.
The pseudo code of the brute force approach is as the following:
We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.
Input
The first line contains an integer T, denoting the number of test cases.
Each test case contains one string in a line consisting of printable ASCII characters except space.
Each test case contains one string in a line consisting of printable ASCII characters except space.
* 1≤T≤30
* string length ≤106 for every string
Output
For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.
Sample Input
3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc
Sample Output
17
7
32
7
32
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<cmath> const int maxn=1e6+;
typedef long long ll;
using namespace std; ll ans;
void pre_EKMP(char x[],int m,ll next[])
{
next[]=m;
int j=;
while(j+<m&&x[j]==x[j+])
{
j++;
} next[]=j;
int k=;
for(int i=;i<m;i++)
{
int p=next[k]+k-;
int L=next[i-k];
if(i+L<p+)next[i]=L;
else
{
j=max(,p-i+);
while(i+j<m&&x[i+j]==x[j])j++; next[i]=j;
k=i;
}
}
} char str[*maxn];
ll nxt[*maxn];
int main()
{
int T;
cin>>T; while(T--)
{
scanf("%s",str);
int len=strlen(str);
ans=; pre_EKMP(str,len,nxt);
for(int t=;t<len;t++)
{
if(nxt[t]+t<len)
{
ans+=(nxt[t]+);
}
else
{
ans+=(len-t);
}
}
// ll ans=0;
printf("%lld\n",ans);
}
return ;
}
最新文章
- POJ 2299 Ultra-QuickSort 线段树
- PrototypePattrn(原型模式)
- 选中多个<;ul>;中的第一个<;li>;方法
- 保存配置文件的appSetting
- 【BZOJ-1857】传送带 三分套三分
- delphi 2007 远程调试
- mysql sql技巧篇
- Linux环境命令大全
- C语言求两个函数中的较大者的MAX函数
- CSS和JS标签style属性对照表
- Echart..js插件渲染报错 data.length<;1?
- At-rule | CSS @ 规则
- javascript判断值是否undefined
- HTML5之Canvas影片广场
- Java并发之线程间的协作
- 浅谈JavaScript的apply和call语句
- 一个模型中有两个外键指向同一张表时,创建迁移模型时报错:“ HINT: Add or change a related_name argument to the definition for &#39;AnswersModel.author&#39; or &#39;AnswersModel.relay_to&#39;.”解决方案
- Windows转Linux总结(附带常用Linux命令-LinuxMint)
- 用友云开放平台之API网关
- Prometheus+AlertManager实现邮件报警