URAL 1684. Jack's Last Word （ KMP next函数应用 ）

题意：问第二行的串能不能恰好分割成几个串，使得这几个串都是第一行串的前缀。如果是，输出No, 并输出这几个串，否则输出Yes。

这题是Special Judge，把两个串连接起来，中间用一个未出现过的字符分隔开。

从新串串尾开始，每次向前移动一个最大前缀的长度。如果期间遇到nextval值为0的点（即没有公共前缀），则肯定不行。

记录分割点位置，输出结果。

#include <cstdio>

#include <cstring>

#include <cstdlib>

const int MAXN = ;

char str[MAXN << ];

char tmp[MAXN];

int nextval[MAXN << ];

int strL, len;

bool flag[MAXN];

void getNext(char s[],int next[])

{

    int length=len;

    int i=,j=-;

    next[]=-;

    while(i<length)

    {

        if(j==-||s[i]==s[j])

        {

            ++i;

            ++j;

            next[i]=j;

        }

        else

            j=next[j];

    }

    return;

}

int main()

{

    while ( scanf( "%s", str ) ==  )

    {

        strL = strlen(str);

        scanf( "%s", tmp );

        str[strL] = '$';

        strcpy( &str[strL+], tmp );

        len = strlen(str);

        getNext( str, nextval );

        //puts(str);

        memset( flag, false, sizeof(flag) );

        bool ok = false;

        for ( int i = len; i > strL+; )

        {

            int tp = nextval[i];

            if ( tp ==  ) ok = true;

            if ( i-(strL+)- >=  ) flag[i-(strL+)-] = true;

            //printf( "i=%d tp=%d\n", i, tp );

            if ( tp >  ) i -= tp;

            else --i;

        }

        if ( ok ) puts("Yes");

        else

        {

            puts("No");

            for ( int i = ; i < len-strL-; ++i )

            {

                putchar( tmp[i] );

                if ( i != len-strL- && flag[i] ) putchar(' ');

            }

            puts("");

        }

    }

    return ;

}