题意:问第二行的串能不能恰好分割成几个串,使得这几个串都是第一行串的前缀。如果是,输出No, 并输出这几个串,否则输出Yes。
这题是Special Judge,把两个串连接起来,中间用一个未出现过的字符分隔开。
从新串串尾开始,每次向前移动一个最大前缀的长度。如果期间遇到nextval值为0的点(即没有公共前缀),则肯定不行。
记录分割点位置,输出结果。
#include#include #include const int MAXN = 75010;char str[MAXN << 1];char tmp[MAXN];int nextval[MAXN << 1];int strL, len;bool flag[MAXN];void getNext(char s[],int next[]){ int length=len; int i=0,j=-1; next[0]=-1; while(i strL+1; ) { int tp = nextval[i]; if ( tp == 0 ) ok = true; if ( i-(strL+1)-1 >= 0 ) flag[i-(strL+1)-1] = true; //printf( "i=%d tp=%d\n", i, tp ); if ( tp > 0 ) i -= tp; else --i; } if ( ok ) puts("Yes"); else { puts("No"); for ( int i = 0; i < len-strL-1; ++i ) { putchar( tmp[i] ); if ( i != len-strL-1 && flag[i] ) putchar(' '); } puts(""); } } return 0;}