首页 > 程序开发 > 软件开发 > C语言 >

HDU 1686 Oulipo

2011-06-21

题意:求模式串在主串中出现的次数【可重叠】 Sample Input 3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN Sample Output 1 3 0   对代码中神奇的地方进行解释:   那么3的意义可以表示为  可见next[len

题意:求模式串在主串中出现的次数【可重叠】

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

对代码中神奇的地方进行解释:

那么3的意义可以表示为

可见next[len2]的意义:前缀和后缀的最长匹配长度

现在就以这个为模式串模拟一下:
主串: A B A B A B C A B A B A A B

模式串:A B A B C A B A

匹配成功后下一步的情况应为:
主串: A B A B A B C A B A B A A B

模式串: A B A B C A B A
指针直接移动到红色部分进行匹配

如何理解呢?
我们先不看最后那2个字符A和B,就可以发现最大前缀【指前缀和后缀的最长匹配长度】直接挪动到最大后缀那里了,为什么可以这样呢?因为前面都是显然不能够匹配成功的
可以向前移动一位试试看:
主串: A B A B A B C A B A B A A B

模式串: A B A B C A B A
我们先不看最后那2个字符A和B,可以看到现在是4长度的前缀与4长度的后缀比较,显然不
可匹配,因为最大匹配长度是3【指前缀和后缀的最长匹配长度】,显然再向前移也不行的


第一次长篇大论,若有错误或不明白之处,请指出
C++代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L1 1000005
#define L2 10005

int len1, len2, next[L2], res;
char s[L1], p[L2];

void get_next ()
{
int k = -1, j = 0;
next[0] = -1;
while (j < len2) //这里必须要推导出next[len2]
{
if (k == -1 || p[k] == p[j])
{
j++, k++;
if (p[k] != p[j])
next[j] = k;
else next[j] = next[k];
}
else k = next[k];
}
/*for (j = 0; j <= len2; j++)
cout << next[j] << ;
cout << endl;*/
}
void kmp ()
{
int i = 0, j = 0;
while (i < len1 && j < len2)
{
if (j == -1 || s[i] == p[j])
i++, j++;
else j = next[j];
if (j >= len2)
res++, j = next[j]; //灰常神奇的地方,用到next[len2],效率大大提高
}
}
int main()
{
int t;
scanf ("%d", &t);
while (t--)
{
scanf ("%s%s", p, s);
len1 = strlen(s);
len2 = strlen(p);
res = 0;
get_next();
kmp ();
printf ("%d ", res);
}
return 0;
}

相关文章
最新文章
热点推荐