HDU 1711 Number Sequence(算法验证)

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

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

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

                                                                                                                                                              我用生命在奋斗——lx_Zz

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

—————————————————————————    华丽的切割线    ————————————————————————————

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

经过验证、发现我刚刚YY的算法目測是正确的、、O(∩_∩)O哈哈~效果还不错。。

。→_→

淡淡改了一下、毕竟都是类似的题、废话不多说、直接上代码：

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int str1[10005];int str2[1000005];int next[10005];int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n,m;        scanf("%d%d",&n,&m);        for(int i=0;i<n;i++)            scanf("%d",&str2[i]);        for(int i=0;i<m;i++)            scanf("%d",&str1[i]);        int len1=m;        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=n;        int ans=-1;        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=i-m+1;                    break;                }            }            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;}