问题 A: 输出next数组

问题 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] ;

    }

}