首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。