`

POJ 2752 Seek the Name, Seek the Fame

    博客分类:
  • KMP
阅读更多
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;
}
13
11
分享到:
评论

相关推荐

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ1027-The Same Game

    【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...

    北大POJ1163-The Triangle

    北大POJ1163-The Triangle

    POJ1163-The Triangle

    【标题】"POJ1163 - The Triangle" 是北京大学在线编程平台POJ上的一道算法题目。这道题目通常被归类为计算机科学与信息技术领域的算法问题,特别是涉及数据结构和动态规划的子领域。 【描述】该题目的解题报告详细...

    北大POJ3267-The Cow Lexicon

    北大POJ3267-The Cow Lexicon

    POJ2635-The Embarrassed Cryptographer

    【标题】"POJ2635 - The Embarrassed Cryptographer" 是一道来源于北京大学在线判题系统POJ(Problem Set)的编程题目。这道题目的主要目标是解决一个与密码学相关的问题,通常这类问题会涉及到算法设计、字符串处理...

    POJ2965-The Pilots Brothers' refrigerator

    在提供的代码文件中,"POJ2965-The Pilots Brothers' refrigerator(DFS+enum).cpp" 应该是使用DFS和枚举实现的解决方案,而 "POJ2965-The Pilots Brothers' refrigerator(DFS+Bit).cpp" 是使用DFS和位运算的版本。...

    POJ3982-The Fibonacci sequence

    【标签】"POJ 3982 The Fibonacci sequence"是这个编程问题的标识,便于搜索和分类。POJ平台上的每个题目都有唯一的标签,方便用户查找和回顾。 斐波那契序列是计算机科学中一个基础而重要的概念,它的定义如下:...

    POJ2635-The Embarrassed Cryptographer 测试数据

    《POJ2635-The Embarrassed Cryptographer:测试数据解析与算法探讨》 POJ2635,这是一个源自NCPC(全国大学生程序设计竞赛)2005年问题D的编程挑战,名为“尴尬的密码学家”。在本文中,我们将深入探讨这个问题的...

    poj 3548 Restoring the digits.md

    poj 3548 Restoring the digits.md

    poj 1611 The Suspects 代码

    poj 1611 The Suspects 代码 并查集的应用

    poj 3554 Almost the shortest route.md

    poj 3554 Almost the shortest route.md

    POJ2151-Check the difficulty of problems

    标题“POJ2151-Check the difficulty of problems”是指一个编程竞赛题目,来源于北京大学的在线判题系统POJ(PKU Online Judge)。这个题目要求参赛者编写程序来评估问题的难度。描述中的“解题报告+AC代码”表明...

    POJ2983-Is the Information Reliable【差分约束+优化Bellman】

    《POJ2983-Is the Information Reliable:解析差分约束与优化Bellman算法》 北京大学在线编程平台上的POJ2983题目——"Is the Information Reliable",是一道涉及差分约束系统(Differential Constraint System)与...

    POJ1207-The 3n + 1 problem

    《POJ1207-The 3n + 1 problem》是北京大学在线编程平台POJ上的一道经典算法题目,其主要涉及的知识点是数论和动态规划。本题目的核心是解决著名的“Collatz Conjecture”问题,也被称为“3n+1猜想”。 3n+1猜想是...

    POJ3267-The Cow Lexicon

    《POJ3267 - The Cow Lexicon》是一道源于北京大学在线判题系统POJ(Problem Online Judge)的编程竞赛题目。这道题目主要涉及数据结构与算法的知识,特别是字符串处理和字典树(Trie)的应用。下面将详细阐述这个...

    POJ 1054 The Troublesome Frog.rar

    标题中的“POJ 1054 The Troublesome Frog”是一个编程竞赛题目,来源于“Programming Online Judge”(POJ)平台。这个平台是程序员们练习算法和编程技能的地方,通常涉及各种数据结构和算法的问题。题目...

    POJ3239-Solution to the n Queens Puzzle

    北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码

    poj 1611 The Suspects.md

    poj 1611 The Suspects.md

    POJ2388-Who's in the Middle

    《POJ2388-Who's in the Middle》是一个典型的计算机编程竞赛题目,主要考察参赛者的算法设计和实现能力。这个题目源自北京大学的在线评测系统POJ(PKU Online Judge),是编程爱好者和学生提升编程技能的重要平台之...

Global site tag (gtag.js) - Google Analytics