HDU 1711 Number Sequence（模板题）
#include <cstdio> const int MAXN = ;
const int MAXL = ; int N, M; int textS[MAXN];
int tarS[MAXL];
int next[MAXL]; void GetNextVal( int* s, int* nextval, int len )
{
int i = , j = -;
nextval[] = -;
while ( i < len )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
nextval[i] = j;
}
else j = nextval[j];
}
return;
} int KMP( int *t, int lent, int *s, int lens )
{
GetNextVal( t, next, lent );
int i = , j = ;
while ( j < lens )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lent ) return j;
}
else i = next[i];
}
return -;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d%d", &N, &M );
for ( int i = ; i < N; ++i ) scanf( "%d", &textS[i] );
for ( int i = ; i < M; ++i ) scanf( "%d", &tarS[i] ); int ans = KMP( tarS, M, textS, N );
if ( ans < ) printf( "%d\n", ans );
else printf("%d\n", ans - M + );
}
return ;
}
HDU 1686 Oulipo（模板题）
#include <cstdio>
#include <cstring>
#include <cstdlib> const int MAXN = ;
const int MAXL = ; char tarS[MAXL];
char testS[MAXN];
int next[MAXL]; void GetNextVal( char *s, int len, int *p )
{
int i = , j = -;
p[] = -;
while ( i < len )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
p[i] = j;
}
else j = p[j];
}
return;
} int KMP( char *t, char *s )
{
int cnt = ;
int lent = strlen(t);
int lens = strlen(s);
GetNextVal( t, lent, next ); int i = , j = ;
while ( j < lens )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lent )
{
++cnt;
i = next[i];
}
}
else i = next[i];
} return cnt;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%s%s", tarS, testS );
printf("%d\n", KMP( tarS, testS ) );
}
return ;
}
HDU 2203 亲和串
#include <cstdio>
#include <cstring>
#include <cstdlib> const int MAXN = ; char testS[ MAXN << ];
char tarS[MAXN];
char temp[MAXN];
int next[MAXN]; void GetNextVal( char *s, int len, int *p )
{
int i = , j = -;
p[] = -;
while ( i < len )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
p[i] = j;
}
else j = p[j];
}
return;
} bool KMP( char *s, int lenS, char *t, int lenT )
{
GetNextVal( t, lenT, next );
int i = , j = ;
while ( j < lenS )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lenT ) return true;
}
else i = next[i];
}
return false;
} int main()
{
while ( ~scanf( "%s", temp ) )
{
scanf("%s", tarS );
int lenS = strlen(temp);
int lenT = strlen(tarS);
if ( lenT > lenS )
{
puts("no");
continue;
} strcpy( testS, temp );
strcpy( &testS[lenS], temp ); KMP( testS, lenS + lenS, tarS, lenT ) ? puts("yes") : puts("no"); }
return ;
}
POJ 3450 Corporate Identity KMP+二分
二分串长，求出每个串长的所有子串，只要找到一个符合的子串即可。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std; const int MAXN = ;
const int MAXL = ; int N;
char str[MAXN][MAXL];
char temp[MAXL];
char anser[MAXL];
int nextval[MAXL];
int len[MAXN]; void GetNextVal( char *s, int lenth )
{
int i = , j = -;
nextval[] = -;
while ( i < lenth )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
if ( s[i] != s[j] ) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
return;
} bool KMP( char *t, char *s, int lenth, int lenn )
{
GetNextVal( t, lenth );
int i = , j = ;
while ( j < lenn )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lenth ) return true;
}
else i = nextval[i];
//if ( i == lenth ) return true;
}
return false;
} bool check( int tpL )
{
bool flag = false;
bool ok = false;
for ( int st = ; st + tpL - < len[]; ++st )
{
for ( int k = ; k < tpL; ++k )
temp[k] = str[][ st + k ];
temp[ tpL ] = '\0';
//puts(temp); ok = true;
for ( int i = ; i < N; ++i )
if ( !KMP( temp, str[i], tpL, len[i] ) )
{
ok = false;
break;
}
if ( ok )
{
flag = true;
if ( anser[] == '\0' ||
( strlen(anser) == strlen(temp) && strcmp( anser, temp ) > ) || ( strlen(anser) < strlen(temp) ) )
strcpy( anser, temp );
}
}
return flag;
} int main()
{
while ( scanf( "%d", &N ), N )
{
int bound = << ;
for ( int i = ; i < N; ++i )
{
scanf( "%s", str[i] );
len[i] = strlen( str[i] );
bound = min( bound, len[i] );
} int low = ;
int high = bound;
int mid, ans = ;
anser[] = '\0';
while ( low <= high )
{
mid = ( low + high ) >> ;
if ( check( mid ) )
{
ans = mid;
low = mid + ;
}
else high = mid - ;
} if ( !ans ) puts("IDENTITY LOST");
else puts(anser);
}
return ;
}
POJ 2752 Seek the Name, Seek the Fame
next函数的应用
#include <cstdio>
#include <cstring>
#include <cstdlib> const int MAXN = ; char str[MAXN];
int next[MAXN];
int ans[MAXN];
int len; void getNext( char *s )
{
int i = , j = -;
next[] = -;
while ( i < len )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
next[i] = j;
}
else j = next[j];
}
return;
} int main()
{
while ( ~scanf( "%s", str ) )
{
len = strlen(str);
getNext( str );
int cnt = ;
ans[] = len;
int i = len;
while ( next[i] > )
{
ans[ ++cnt ] = next[i];
i = next[i];
}
for ( ; cnt >= ; --cnt )
{
printf( "%d", ans[cnt] );
if ( cnt ) putchar(' ');
}
puts("");
}
return ;
}
HDU 2087 剪花布条
求一个串在另一个串中的出现次数，KMP模板题
#include <cstdio>
#include <cstring>
#include <cstdlib> const int MAXN = ; char str[MAXN];
char tmp[MAXN];
int nextval[MAXN];
int cnt; void getNextval(char *s, int *nextval, int length )
{
int i=,j=-;
nextval[]=-;
while(i<length)
{
if(j==-||s[i]==s[j])
{
++i;
++j;
//next[i]=j;
if (s[i]!=s[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
} void KMP( char *t, char *s ) //s为主串，t为模式串
{
int lenth = strlen(t);
int len = strlen(s);
getNextval( t, nextval, lenth );
int i = , j = ;
while ( j < len )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lenth )
{
++cnt;
i = ;
}
}
else i = nextval[i];
}
return;
} int main()
{
while ( scanf( "%s", str ) == && str[] != '#' )
{
scanf( "%s", tmp );
cnt = ;
KMP( tmp, str );
printf( "%d\n", cnt );
}
return ;
}
HDU 2594 Simpsons’ Hidden Talents （next函数应用）
把两个串连接起来，中间用一个没出现过的字符分隔开，直接输出最后一个字符的next的值。
#include <cstdio>
#include <cstring>
#include <cstdlib> using namespace std; const int MAXN = ; char str[MAXN << ];
char tmp[MAXN];
int nextval[MAXN << ];
int length; void getNext(char s[],int next[])
{
length=strlen(s);
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%s", str, tmp ) == )
{
int len = strlen(str);
str[len] = '$';
str[len + ] = '\0';
strcat( str, tmp );
getNext( str, nextval );
str[ nextval[length] ] = '\0';
if ( nextval[length] > )
printf( "%s %d\n", str, nextval[length] );
else puts("");
}
return ;
}
URAL 1423. String Tale ( KMP模板题 )
#include <cstdio>
#include <cstring>
#include <cstdlib> using namespace std; const int MAXN = ; int nextval[MAXN << ];
char str[MAXN << ];
char tmp1[MAXN];
char tmp2[MAXN];
int len; void getNextval( char s[],int nextval[], int length )
{
int i=,j=-;
nextval[]=-;
while(i<length)
{
if(j==-||s[i]==s[j])
{
++i;
++j;
//next[i]=j;
if (s[i]!=s[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
} int KMP( char *t, char *s ) //s为主串，t为模式串
{
int lenth = strlen(t);
int len = strlen(s);
getNextval( t, nextval, lenth );
int i = , j = ;
while ( j < len )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lenth ) return j;
}
else i = nextval[i];
}
return -;
} int main()
{
while ( scanf( "%d", &len ) == )
{
scanf( "%s%s", tmp1, tmp2 );
strcpy( str, tmp1 );
strcat( str, tmp1 );
int ans = KMP( tmp2, str );
//printf( "ans = %d\n", ans );
if ( ans == - ) puts("-1");
else if ( ans == len ) puts("");
else printf( "%d\n", len + len - ans );
}
return ;
}