Seek the Name, Seek the Fame

Time Limit: 2000MS Memory Limit: 65536K

Total Submissions: 13619 Accepted: 6755

Description

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father’s name and the mother’s name, to a new string S.

Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father=’ala’, Mother=’la’, we have S = ‘ala’+’la’ = ‘alala’. Potential prefix-suffix strings of S are {‘a’, ‘ala’, ‘alala’}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

Input

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

Output

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby’s name.

Sample Input

ababcababababcabab

aaaaa

Sample Output

2 4 9 18

1 2 3 4 5

题意是求一个字符串,前缀和后缀相等的有多少,分别由小到大输出其长度。

想到方法的时候觉得这题出得真是亮,之前学KMP算法的时候,没觉得next数组有那么多的用处,这回做了三道KMP题之后,也算是好好理解了next数组。

一个字符串s,长度为n。其中字符使用s[0],s[1],s[2]—-s[n-1]。

其中next[i]表示的含义是字符串s在位置i之前,有多少个 和字符串从头开始数 相等的数量,具体来说什么意思,就是比方说next[i]=k ,说明s[0]s[1]s[2]–s[k-1] = s[i-k] –s[i-3]s[i-2]s[i-1]。这个也是求next数组时候的方法,判断s[i]==s[j],之后i++,j++。最后赋值next[i]=j。所以next[i]实际表示的是在字符i之前的情况。

所以说我next[n]=k的话 (n是整个字符串的长度),表示的就是这个字符串里面最大有多少k个字符满足s[0]s[1]s[2]–s[k-1] = s[n-k] –s[n-3]s[n-2]s[n-1],而这不恰恰是所满足的其中一项吗?

求了这个next[n]=k之后,接下来要求的就是next[k]了,因为你都满足了s[0]s[1]s[2]–s[k-3]s[k-2]s[k-1] = s[n-k] --s[n-3]s[n-2]s[n-1]这个条件,即后缀字符串是相同的,那我只需缩小范围即可,缩小到s[0]–s[k-1],求next[k]即可。之后就以此类推,不断查询,知道next[]=0。因为题目要求从大到小输出,所以把每一个记录下来,再重新输出即可。

代码:

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std; char a[400005];
int next1[400005];
int len;
vector<int> result; void cal()
{
int i,j=-1;
next1[0]=-1;
for(i=0;i<len+1;)
{
if(j==-1||a[i]==a[j])
{
i++;
j++;
next1[i]=j;
}
else
{
j=next1[j];
}
} } int main()
{
while(cin>>a)
{
len = strlen(a);
cal(); int temp = len;
while(next1[temp])
{
result.push_back(next1[temp]);
temp=next1[temp];
}
sort(result.begin(),result.end()); int i;
for(i=0;i<result.size();i++)
{
cout<<result[i]<<" ";
}
cout<<len<<endl;
result.clear();
} return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

最新文章

  1. laravel 获取 当前url 的方法, 有的是获取 全部url 有的只获取 主页其他 部分
  2. js数组常用方法汇总
  3. (C#) 基本概念一览表
  4. Java面试之SE基础基本数据类型
  5. linux mail 配置
  6. DICOM开源库
  7. Owasp Top 10 Security Risks for 2014
  8. windows套接字相关函数
  9. L10 安装网卡驱动
  10. Session和Cookie的关系
  11. 简单天气应用开发——解析HeWeather JSON
  12. 启用Apache Mod_rewrite模块
  13. BZOJ 3545: [ONTAK2010]Peaks [Splay启发式合并]
  14. Linux内核的冷热缓存
  15. STM32串口空闲中断
  16. 单调队列以及单调队列优化DP
  17. 阅读Google Protocol Buffers 指南,整理pb语法
  18. 用十条命令在一分钟内检查 Linux 服务器性能
  19. linux 修改文件类型
  20. PCMU G.711U/PCMA G.711A简介

热门文章

  1. java#临时文件目录
  2. 「NOI2015」软件包管理器
  3. mybatis关键查询
  4. 【剑指Offer面试编程题】题目1348:数组中的逆序对--九度OJ
  5. String类与StringBuffer类
  6. JDK8中的ConcurrentHashMap源码
  7. 096、Java中String类之手工入对象池操作
  8. leetcode813 Largest Sum of Averages
  9. ubuntu 系统分配固定 ip--
  10. NO18 linux开机自启动设置--开机流程--中文乱码--查看行数