hdu 3336 Count the string(KMP)
string The HDU count KMP
2023-09-27 14:25:13 时间
一道应用kmp算法中next数组的题目
这当中vis[i]从1加到n
vis[i]=[next[i]]+1;
#include<string.h>#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
char s[200005];
int b;
int next[200005];
int vis[200005];
void nest(char *s)
{
next[0]=-1;
int i=0;
int j=-1;
while(i<b)
{
if(j==-1||s[i]==s[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
// for(i=0;i<=b;i++)
// printf("%d\n",next[i]);
}
bool kmp(char *s)
{
int sum=0;
for(int k=1;k<=b;k++)
{
/*int i=0,j=0;
while(i<b)
{
if(j==-1||s[i]==s[j])
{
i++;j++;
if(j==k)
{
sum++; //printf("%d\n",j);
j=next[j];
}
}
else j=next[j];
}*/
if(next[k]==0)
vis[k]=1;
else
vis[k]=vis[next[k]]+1;
}
}
int main()
{
int a;
scanf("%d",&a);
while(a--)
{
memset(vis,0,sizeof(vis));
scanf("%d",&b);
scanf("%s",s);
int sum=0;
nest(s);
kmp(s);
for(int i=1;i<=b;i++)
{sum+=vis[i];
sum=sum%10007;}
printf("%d\n",sum);
}
}
相关文章
- rust 中的 String 和 &str
- 与string容易混淆的类——StringBuilder
- The request was rejected because the URL contained a potentially malicious String "//"
- @RequestParam注解使用:Name for argument type [java.lang.String] not available, and parameter name information not found in class file either.
- es版本2.x的string和5.x的keyword,text的区别和联系
- String.Format( )用法
- STRING DELIMITED BY SIZE
- selenium 难定位元素,时间插件,下拉框定位,string
- 构造UTF8的std::string
- java-基础-String、StringBuilder以及StringBuffer剖析
- C++ string的用法和例子
- Java常量字符串String理解 String理解
- HDOJ3374 String Problem 【KMP】+【最小表示法】
- JavaScript(JS) string.sup( )
- JavaScript(JS) string.localeCompare( param )
- String or binary data would be truncated. The statement has been terminated.
- tomcat 7 WARNING: A context path must either be an empty string or start with a '/' and do not end with a '/'. The path [/] does not meet these criteria and has been changed to []
- 面试题系列第6篇:JVM字符串常量池及String的intern方法详解?