首页 > 代码库 > poj 1056 IMMEDIATE DECODABILITY

poj 1056 IMMEDIATE DECODABILITY

题目链接:http://poj.org/problem?id=1056

 

思路:

检测某字符串是否为另一字符串的前缀,数据很弱,可以使用暴力解法。这里为了练习KMP算法使用了KMP算法。

 

代码:

 

#include <iostream>using namespace std;const int N = 10;const int Len = 20;char A[N][Len];int Next[N][Len];void get_nextval( char P[], int Next[] ){    int i = 0, j = -1;    int PLen = strlen(P);    Next[0] = -1;    while ( i < PLen - 1 )    {        if ( j == -1 || P[i] == P[j] )        {            i++;            j++;            if ( P[i] == P[j] )                Next[i] = j;            else                Next[i] = Next[j];        }        else            j = Next[j];    }}int KMP_Matcher( char T[], char P[], int Next[] ){    int i = 0, j = 0;    int TLen = strlen( T );    int PLen = strlen( P );    while ( i < TLen && j < PLen )    {        if ( j == -1 || T[i] == P[j] )        {            i++;            j++;        }        else            j = Next[j];    }    if ( j == PLen )        return i - j;    else        return -1;}int main( ){    int Count = 0, flag = -1, n = 0;    while ( scanf( "%s\n", A[Count] ) != EOF )    {        if ( A[Count][0] == 9 )        {            n++;            for( int i = 0; i < Count; ++i )                get_nextval( A[i], Next[i] );            for ( int i = 0; i < Count - 1; ++i )                for ( int j = i + 1; j < Count; ++j )                {                    if ( flag == 0 )                        break;                    flag = KMP_Matcher( A[j], A[i], Next[i] );                }            if ( flag == 0 )                printf( "Set %d is not immediately decodable\n", n );            else                printf( "Set %d is immediately decodable\n", n );                        Count = 0;            flag = -1;            continue;        }        Count++;    }        return 0;}

 

poj 1056 IMMEDIATE DECODABILITY