【HDU2087】KMP
2024-08-27 23:14:17
KMP算法其实很好理解,就是在匹配串中找最近的相同的串。
下面是HDU的2087:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define maxn 1005
using namespace std;
string s1,s2;
int f[maxn],ans;
void kmp(string &x,string &y)
{
int le=x.size(),j=,ll=y.size();
for (int i=;i<le;i++)
{
while (j&&x[i]!=y[j])
j=f[j];
if (x[i]==y[j]) j++;
if (j==ll) {
ans++;//j=0;
}
}
}
void find(string &x)
{
int ll=x.size(),j=;
f[]=;f[]=;
for (int i=;i<ll;i++)//从第二个点开始
{
j=f[j];
while (j&&x[j]!=x[i]) j=f[j];
f[i+]= x[j]==x[i] ? j+ : ;
}
}
int main()
{
//freopen("2087kmp.in","r",stdin);
while (cin>>s1&&s1[]!='#')//cin不读空格
{
cin>>s2;
memset(f,,sizeof (f));
ans=;
find(s2);
kmp(s1,s2);
cout<<ans<<endl;
}
return ;
}
最新文章
- Linux打包与压缩及tar命令详解
- 再解java中的String
- c++错误——intermediate.manifest : general error c1010070很傻的错
- Saltstack之Syndic(十)
- oralce CASE WHEN 用法
- graph-tool文档(一)- 快速开始使用Graph-tool - 2.属性映射、图的IO和Price网络
- redis的启动与停止
- Windows环境变量
- Please check if the Publishing Tools on the server (System/PublishingTools) are started.
- Spring注解基本解读
- 【拓扑排序】【线段树】Gym - 101102K - Topological Sort
- read命令读取用户输入
- iOS开发中如何创建多个target
- MapReduce-实践1
- Tomcat8配置Https协议,Tomcat配置Https安全访问,Tomcat Https配置
- Linux网络配置(setup)
- 报错:org.apache.hadoop.hive.metastore.HiveMetaException: Failed to get schema version.
- Java异常处理的方法
- java算法大全
- 如何认识TOS----DSCP 对照表