首页 > 代码库 > Hdu 1686 Oulipo
Hdu 1686 Oulipo
Problem地址：http://acm.hdu.edu.cn/showproblem.php?pid=1686
字符串匹配，因此采用了KMP算法。有一点需要注意，请看题目的样例2：
T: AZA
S: AZAZAZ
很明显T和S的前3位匹配，那么接下来呢？
我最初设计的程序，T和S的前三位匹配后，T开始与S的第四位进行匹配判断。
但实际上，S的第三位至S的第五位可以与T匹配。
为什么会这样呢？
我思考了之后明白了问题所在：当T在S中找到一个匹配串后，T将第一位与S的下一位进行比较。这实际上可能造成失去发现一个新字符串匹配的机会。
因此，当T在S中找到一个匹配串后，T不应将第一位与S的下一位进行比较。那应该将T的第几位比呢？其实思考一下就可以知道怎么办。
将T与自己匹配，当比较结束后，看一下作为待匹配的T最多与模式串T的第几位匹配即可。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int W_MAXN = 10000 + 50;char word[ W_MAXN ];int next[ W_MAXN ];const int T_MAXN = 1000000 + 50;char text[ T_MAXN ];int End;void Get_next() // 得到next数组{ int i, j = 0; next[ 1 ] = 0; int length = strlen( word+1 ); for( i=2;i<=length;i++ ) { next[i] = j; if( word[i]!=word[ j+1 ] ) { j = next[ j+1 ]; } else { j ++; } }}void Get_End(){ int i, j = 0; int finish = strlen ( word+1 ); for( i=2; i<=finish;i++ ) { while( j>0 && word[i]!=word[j+1] ) { j = next[ j+1 ]; } if( word[i]==word[j+1] ) { j ++; } } End = j;}int Count(){ int counter = 0; int i, j = 0; int finish = strlen ( word+1 ); int length = strlen ( text+1 ); for( i=1;i<=length;i++ ) { while( j>0 && text[i]!=word[ j+1 ] ) { j = next[ j+1 ]; } if( text[i] == word[j+1] ) { j ++; } if( j==finish ) { j = End; // 不应 j = 0 counter ++; } } return counter;}int main(){ int T; scanf( "%d", &T ); while( T-- ) { scanf( "%s", word+1 ); scanf( "%s", text+1 ); // 为方便， 均从第一位读起 Get_next(); Get_End(); printf( "%d\n", Count() ); } return 0;}
Hdu 1686 Oulipo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。