http://poj.org/problem?id=2752
题意:找出所给串的所有前缀长度,使得所给串中这个长度的前缀==这个长度的后缀
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
看了HDU 1686 Oulipohttp://972169909-qq-com.iteye.com/blog/1070507
相信next值的意义就很清晰了
下面给出描述: (i>1)[下标从0开始]
next[i]的意义就是:前面长度为i的字串的【前缀和后缀的最大匹配长度】
那么这题怎么利用这个性质呢?
详细分析一下:【就用上面的第一个例子说明吧】
求出next值:[非修正] |
下标: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
串: a b a b c a b a b a b a b c a b a b |
|
next值: -1 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9 |
len2 = 18 next[len2] = 9
说明对于前面长度为18的字符串,【长度为9的前缀】和【长度为9的后缀】是匹配的, 即上图的蓝色跟红色匹配
也就是整个串的最大前后缀匹配长度就是9了
所以接下来根本不需要考虑长度大于9的情况啦
好了!既然现在只需考虑长度小于9的前后缀匹配情况,那么
[问题就转化成蓝色串的前缀跟红色串的后缀的匹配问题了!!!
又因为蓝串==红串
所以问题又转化成
找蓝串自己的前缀跟自己的后缀的最大匹配了!!!
那么我们现在就要找next[9]的值了【next[9]的含义:蓝串的最大前后缀匹配】
回忆第一步:我们找的是next[len2]=9【len2=18】
怎么使得第二部目标变成9【求next[9]】呢?
其实next[len2]=9同时可以表示为:最大匹配前后缀的【前缀长度】
那么next[9]的意义就是:
【主串】的最大匹配前后缀的【前缀】的【最大匹配前后缀】了!!
也就是上面蓝串的前后缀最大匹配长度了!!
那么算法描述就是:
第一步:求next[len2], 即next[18] = 9;
第二步:把9代进来,即求next[9] = 4;
第三步:把4代进来,即求next[4] = 2;
第四步:next[2] = 0; 也就是下标2之前的串已经没有前后缀可以匹配了
所以答案就是: 2 4 9 18 【PS: 从小到大输出,18是串长,显然符合题意】
局部实现代码:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define L2 400005
int next[L2], len2, ans[L2];
char p[L2];
bool hash[L2];
void get_next()
{
int k = -1, j = 0;
next[0] = -1;
while (j < len2)
{
if (k == -1 || p[j] == p[k])
{
j++, k++;
next[j] = k;
}
else k = next[k];
}
}
int main()
{
int k, i, j;
while (scanf ("%s", p) != EOF)
{
k = 0;
memset (hash, false, sizeof(hash));
len2 = strlen (p);
get_next();
j = next[len2];
while (j > 0)
ans[k++] = j, j = next[j];
for (i = k - 1; i >= 0; i--) //倒过来输出,就是从小到大了
printf ("%d ", ans[i]);
printf ("%d\n", len2);
}
return 0;
}
分享到:
相关推荐
【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...
【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...
北大POJ1163-The Triangle
【标题】"POJ1163 - The Triangle" 是北京大学在线编程平台POJ上的一道算法题目。这道题目通常被归类为计算机科学与信息技术领域的算法问题,特别是涉及数据结构和动态规划的子领域。 【描述】该题目的解题报告详细...
北大POJ3267-The Cow Lexicon
【标题】"POJ2635 - The Embarrassed Cryptographer" 是一道来源于北京大学在线判题系统POJ(Problem Set)的编程题目。这道题目的主要目标是解决一个与密码学相关的问题,通常这类问题会涉及到算法设计、字符串处理...
在提供的代码文件中,"POJ2965-The Pilots Brothers' refrigerator(DFS+enum).cpp" 应该是使用DFS和枚举实现的解决方案,而 "POJ2965-The Pilots Brothers' refrigerator(DFS+Bit).cpp" 是使用DFS和位运算的版本。...
【标签】"POJ 3982 The Fibonacci sequence"是这个编程问题的标识,便于搜索和分类。POJ平台上的每个题目都有唯一的标签,方便用户查找和回顾。 斐波那契序列是计算机科学中一个基础而重要的概念,它的定义如下:...
《POJ2635-The Embarrassed Cryptographer:测试数据解析与算法探讨》 POJ2635,这是一个源自NCPC(全国大学生程序设计竞赛)2005年问题D的编程挑战,名为“尴尬的密码学家”。在本文中,我们将深入探讨这个问题的...
poj 3548 Restoring the digits.md
poj 1611 The Suspects 代码 并查集的应用
poj 3554 Almost the shortest route.md
标题“POJ2151-Check the difficulty of problems”是指一个编程竞赛题目,来源于北京大学的在线判题系统POJ(PKU Online Judge)。这个题目要求参赛者编写程序来评估问题的难度。描述中的“解题报告+AC代码”表明...
《POJ2983-Is the Information Reliable:解析差分约束与优化Bellman算法》 北京大学在线编程平台上的POJ2983题目——"Is the Information Reliable",是一道涉及差分约束系统(Differential Constraint System)与...
《POJ1207-The 3n + 1 problem》是北京大学在线编程平台POJ上的一道经典算法题目,其主要涉及的知识点是数论和动态规划。本题目的核心是解决著名的“Collatz Conjecture”问题,也被称为“3n+1猜想”。 3n+1猜想是...
《POJ3267 - The Cow Lexicon》是一道源于北京大学在线判题系统POJ(Problem Online Judge)的编程竞赛题目。这道题目主要涉及数据结构与算法的知识,特别是字符串处理和字典树(Trie)的应用。下面将详细阐述这个...
标题中的“POJ 1054 The Troublesome Frog”是一个编程竞赛题目,来源于“Programming Online Judge”(POJ)平台。这个平台是程序员们练习算法和编程技能的地方,通常涉及各种数据结构和算法的问题。题目...
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
poj 1611 The Suspects.md
《POJ2388-Who's in the Middle》是一个典型的计算机编程竞赛题目,主要考察参赛者的算法设计和实现能力。这个题目源自北京大学的在线评测系统POJ(PKU Online Judge),是编程爱好者和学生提升编程技能的重要平台之...