POJ 3461 Oulipo（自己YY的模式匹配算法）

请不要随便指点别人该怎么做、每个人的人生都应该自己掌握、你给不了别人一切、你也不懂别人的忧伤、

                                                                                        微笑不代表快乐、哭泣不一定悲伤

               不努力怎么让关心你的人幸福、不努力怎么让看不起你的人绝望、

                                                                                                                                                              我用生命在奋斗——lx_Zz

—————————————————————————————————————————————————————————————

—————————————————————————    华丽的分割线    ————————————————————————————

—————————————————————————————————————————————————————————————

看各种大牛的文章看了两个小时、关于模式匹配有很多种算法、KMP、BM、还有吊炸天编译原理的DFA的正则文法匹配、简直只能ORZ。。。

决心不看模板、根据思想自己YY、果然还是让我YY出来了。。。别告诉我是POJ数据太弱。。。那我想死的心都有了→_→

好吧、一会儿再切几道题看看是不是水过去的、

其实思想很简单、由于直接BF算法是肯定会TLE、最开始我写了一遍、TLE了之后、开始YY模式匹配、为了消除回溯、我们可以根据已有的信息来判断从前面某一个开始重新匹配、不一定要从头开始、其实这些都是扯淡的。。。

我说我自己的思考过程好了、我先自己随便举一个例子要匹配的串是“abacabx”、文本串是“abacabwab”

前面都是一样的直接跳过、当x和w不一样的时候、我们是不是一定要重新从下一个字符开始找呢？

仔细模拟一下、你会发现其实就是跳到了第二个ab那里、我们从ab后面那个字符拿来比较就行了、对不对？

这样是不是节约了很多时间、

那就转化成了求对于每个当前字符、它的前缀和后缀最长相等是多少、

比如：abcab 当前最长的前缀和后缀相等ab是2

嗯、那么知道了这个、怎么在线性时间内求解这个辅助数组的值呢？

我自己YY的是分三种情况考虑、

1、首先判断是否可以接在前一个的后面

2、如果不能、则看是否和首字符相等、相等为1

3、不等为0

然后求出这个辅助之后就是遍历的时候如果不等就根据辅助的值来变化模式串的匹配位置

表述不是很清楚、不过代码写的很详细、

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

char str1[10005];
char str2[1000005];
int next[10005];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",str1,str2);
        int len1=strlen(str1);
        next[0]=-1;
        for(int i=1;i<len1;i++)
        {
            if(str1[i]==str1[next[i-1]])
            {
                next[i]=next[i-1]+1;
            }
            else if(str1[i]==str1[0])
            {
                next[i]=1;
            }
            else next[i]=0;
        }
        int len2=strlen(str2);
        int ans=0;
        int flag=0;
        for(int i=0,j=0;i<len2;)
        {
            int ff=0;
            if(str1[j]==str2[i])
            {
                i++;j++;
                if(j>=len1)
                {
                    ans++;
                    j=next[j-1];
                }
            }
            else
            {
                while(str1[j]!=str2[i])
                {
                    if(j==0)
                    {
                        ff=1;
                        break;
                    }
                    j=next[j-1];
                    if(j==-1)
                    {
                        ff=1;
                        break;
                    }
                }
                if(ff)
                {
                    if(str1[0]==str2[i])
                    {
                        i++;j=1;
                    }
                    else
                    {
                        i++;j=0;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

POJ 3461 Oulipo（自己YY的模式匹配算法）,布布扣,bubuko.com

POJ 3461 Oulipo（自己YY的模式匹配算法）

原文：http://blog.csdn.net/a1dark/article/details/25013783