问题 A: 输出next数组

时间限制: 1 Sec  内存限制: 128 MB
提交: 31  解决: 20
[提交][状态][讨论版][
命题人:quanxing][Edit] [TestData]

题目链接:http://acm.ocrosoft.com/problem.php?cid=1717&pid=0

题目描述

在求解KMP过程中,会先求解next数组,给定一个字符(长度不超过40),输出对应next数组。

具体描述:

  给定一个字符串t,如 abcdabc,把从第一个字符开始的t的子串称为t的前缀,如a,ab,abc,abcd...

  给定一个字符串t,如 abcdabc,把从某一个字符开始到最后一个字符的t子串称为t的后缀,如c,bc,abc,dabc,cdabc...

  求出t的子串对应的 前缀长度等于后缀长度 的值  next数组。

 a      ab    abc   abcd   abcda  abcdab   abcdabc

    0        0        0        0         1          2              3

前缀子串和后缀子串:对模式P以及某个位置j,存在最大的k值,使得:p0p1…pk = pj-kpj-k+1…pj(注意k不能等于j,否则等式左右两边是同一个字符串)

输入

一个字符串

输出

对应的next数组。

样例输入

abcabceabcabca

样例输出

00012301234564

思路:用2个指针去匹配,匹配同时++,不匹配j = Next[j]

代码:

#include<bits/stdc++.h>

using namespace std;

int Next[10000];

void get_next(string child)

{

    memset(Next, 0, sizeof(Next));

    int i = 0;

    int j = -1;

    Next[0] = -1;//初始化Next数组

    while (i < child.length())

    {

         if (j == -1 || child[i] == child[j])//匹配或第一次

         {

             ++i;

             ++j;

             Next[i] = j;

         }

         else

         {

             j = Next[j];

         }

    }

}

int main()

{

    string child;

    cin >> child;

    get_next(child);

    for (int i = 1; i <= child.length(); i++)

    {

         cout << Next[i] ;

    }

}