设为首页 加入收藏

TOP

HDU 1686 Oulipo
2014-11-23 22:13:00 来源: 作者: 【大 中 小】 浏览:0次
Tags：HDU 1686 Oulipo

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

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
#include
#include
#include
#include
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}

【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：const的几个用法 下一篇：struct结构体内的对齐问题

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: