[ 登录注册 ]

Java

HDU 1686 Oulipo

2016/08/25 12:04 [db:作者] 返回上一页

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

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

下面给出描述: (i>1)[下标从0开始]
next[i]的意义就是:前面长度为i的字串的【前缀和后缀的最大匹配长度】

那么这题怎么利用这个性质呢?

详细分析一下:【就用上面的第一个例子说明吧】
求出next值:[非修正]
下标:      0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17
串:          a  b  a  b  c  a  b  a  b  a  b   a   b   c   a   b   a   b
next值:  -1  0  0  1  2  0  1  2  3  4  3   4   3   4   5   6   7   8   9

len2 = 18    next[len2] = 9
说明对于前面长度为18的字符串,【长度为9的前缀】和【长度为9的后缀】是匹配的, 即上图的蓝色跟红色匹配
也就是整个串的最大前后缀匹配长度就是9了
所以接下来根本不需要考虑长度大于9的情况啦

好了!既然现在只需考虑长度小于9的前后缀匹配情况,那么
[问题就转化成蓝色串的前缀跟红色串的后缀的匹配问题了!!!
又因为蓝串==红串
所以问题又转化成
找蓝串自己的前缀跟自己的后缀的最大匹配了!!!
那么我们现在就要找next[9]的值了【next[9]的含义:蓝串的最大前后缀匹配】

回忆第一步:我们找的是next[len2]=9【len2=18】
怎么使得第二部目标变成9【求next[9]】呢?
其实next[len2]=9同时可以表示为:最大匹配前后缀的【前缀长度】
那么next[9]的意义就是:
【主串】的最大匹配前后缀的【前缀】的【最大匹配前后缀】了!!
也就是上面蓝串的前后缀最大匹配长度了!!

那么算法描述就是:
第一步:求next[len2], 即next[18] = 9;
第二步:把9代进来,即求next[9] = 4;
第三步:把4代进来,即求next[4] = 2;
第四步:next[2] = 0; 也就是下标2之前的串已经没有前后缀可以匹配了
所以答案就是: 2 4 9 18 【PS: 从小到大输出,18是串长,必然符合题意】
局部实现代码:

C++代码 
j = next[len2]; 
while (j > 0) 
    ans[k++] = j, j = next[j];    //ans储存答案 


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 L2 400005 
 
int next[L2], len2, ans[L2]; 
char p[L2]; 
bool hash[L2]; 
 
void get_next()    //原始next函数 

    int k = -1, j = 0; 
    next[0] = -1; 
    while (j < len2) 
    { 
        if (k == -1 || p[j] == p[k]) 
        { 
            j++, k++; 
            next[j] = k; 
        } 
        else k = next[k]; 
    } 
    /*for (j = 0; j <= len2; j++)
        cout << next[j] << ;
    cout << endl;*/ 

int main() 

    int k, i, j; 
    while (scanf ("%s", p) != EOF) 
    { 
        k = 0; 
        memset (hash, false, sizeof(hash)); 
        len2 = strlen (p); 
        get_next(); 
        j = next[len2]; 
        while (j > 0) 
            ans[k++] = j, j = next[j]; 
        for (i = k - 1; i >= 0; i--)    //倒过来输出,就是从小到大了 
            printf ("%d ", ans[i]); 
        printf ("%d ", len2); 
    } 
    return 0; 

点击复制链接 与好友分享!回本站首页

文章来源:http://www.bozhiyue.com/java/2016/0825/428857.html
评论
发表评论