做此题,只要理解好next数组就行.......................
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
char str[411111],tmp[411111];
int next[411111],ans[411111]; void getnext(char *t) {
int i=0,j=-1;
int len = strlen(t);
next[0] = -1;
while(i < len) {
if(t[i] == t[j] || j == -1) {
i ++;
j ++;
next[i] = j;
} else j = next[j];
}
}
/*
int kmp(char *s,char *t) {
int lens = strlen(s);
int lena = strlen(t);
int i=0,j=0;
while(i < lens && j < lena) {
if(s[i] == t[j] || j == -1) {
i++;
j++;
} else j = next[j];
}
if(j < lena) return -1;
return i - lena;
}
*/
int main() {
while(scanf("%s",str) != EOF) {
strcpy(tmp,str);
int len = strlen(str);
int cnt = 0;
getnext(str);
int j = next[len];
ans[cnt++] = j;
while(j > 1) {
ans[cnt++] = next[j];
j = next[j];
}
for(int i=cnt-1; i>=0; i--) {
if(ans[i] != 0)
printf("%d ",ans[i]);
}
printf("%d\n",len);
}
return 0;
}
POJ 2752 Seek the Name, Seek the Fame(next数组的理解)的更多相关文章
-
poj 2406:Power Strings(KMP算法,next[]数组的理解)
Power Strings Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 30069 Accepted: 12553 D ...
-
(KMP)Seek the Name, Seek the Fame -- poj --2752
http://poj.org/problem?id=2752 Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536 ...
-
Seek the Name, Seek the Fame POJ - 2752
Seek the Name, Seek the Fame POJ - 2752 http://972169909-qq-com.iteye.com/blog/1071548 (kmp的next的简单应 ...
-
KMP POJ 2752 Seek the Name, Seek the Fame
题目传送门 /* 题意:求出一个串的前缀与后缀相同的字串的长度 KMP:nex[]就有这样的性质,倒过来输出就行了 */ /************************************** ...
-
POJ 2752 Seek the Name, Seek the Fame [kmp]
Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 17898 Ac ...
-
poj 2752 Seek the Name, Seek the Fame(KMP需转换下思想)
Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 10204 Ac ...
-
poj 2752 Seek the Name, Seek the Fame【KMP算法分析记录】【求前后缀相同的子串的长度】
Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 14106 Ac ...
-
POJ 2752 Seek the Name, Seek the Fame(next数组运用)
Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 24000 ...
-
POJ 2752 Seek the Name,Seek the Fame(KMP,前缀与后缀相等)
Seek the Name,Seek the Fame 过了个年,缓了这么多天终于开始刷题了,好颓废~(-.-)~ 我发现在家真的很难去学习,因为你还要陪父母,干活,做家务等等 但是还是不能浪费时间啊 ...
随机推荐
-
查看当前正在被执行的sql
由于在公司服务器上在某个时段查询某个sql执行比较慢,由来查询当前正在被执行的sql Select t.text,SUBSTRING(t.text, (r.statement_start_offset ...
-
W5500 keep-alive的用途及使用
大家是否遇到过这种问题,W5500作为server已经建立连接,突然网线掉了,然后再去连接W5500.就连不上了. 为什么?以下对这个问题进行解释说明,并提出解决的方法. 图1中的上位机程序作为cli ...
-
poj 1456 Supermarket(并查集维护区间)
题意:有一些货物,每一个货物有价值和卖出的截至日期,每天能够卖一个货物,问能卖出的最大价值是多少. 思路:算法不难想到,按价值降序排列.对于每一件货物,从deadline那天開始考虑.假设哪天空 ...
-
com.mysql.jdbc.exceptions.MySQLSyntaxErrorException错误
com.mysql.jdbc.exceptions.MySQLSyntaxErrorException: You have an error in your SQL syntax; check the ...
-
vue router mode模式在webpack 打包上线问题
vue-router mode模式有两种 hash和history. 1.hash —— 即地址栏 URL 中的 # 符号.比如这个 URL:http://www.abc.com/#/hello,ha ...
- Java学习图
-
Java8 Hash改进/内存改进
又开新坑o(*≧▽≦)ツ讲讲几个Java版本的特性,先开始Java8, HashMap的改进 HashMap采用哈希算法,先使用hashCode()判断哈希值是否相同,如果相同,再使用equals() ...
-
工资薪金VS劳务报酬
工资薪金所得与劳务报酬所得两个征税项目在个人所得税应纳税所得额的计算.征收标准等方面都有所不同,因而在实际操作中不可相互混淆. 工资薪金所得属于非独立个人劳务活动,即在机关.团体.学校.部队.企事业单 ...
-
新手windows安装nginx
windows安装nginx,下载地址:http://nginx.org/download/ 下载的时候,下载 .zip 后缀的压缩包,因为 .zip 的压缩包有nginx.exe 启动文件,其他没有 ...
-
Python3基础 str format 位置参数与关键字参数
Python : 3.7.0 OS : Ubuntu 18.04.1 LTS IDE : PyCharm 2018.2.4 Conda ...