学密码学一定得学程序

心已赠人 2022-08-10 08:41 182阅读 0赞

## 学密码学一定得学程序 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

曾经，ZYJ同学非常喜欢密码学。有一天，他发现了一个很长很长的字符串S1。他很好奇那代表着什么，于是神奇的WL给了他另一个字符串S2。但是很不幸的是，WL忘记跟他说是什么意思了。这个时候，ZYJ不得不求助与伟大的ZP。ZP笑了笑说，这个很神奇的，WL的意思是只要你找到她给你的字符串在那个神奇的字符串的位置，你就会有神奇的发现。ZYJ恍然大悟，原来如此，但是悲剧来了，他竟然不知道怎么找。。。。是的，很囧是不是。所以这时候就需要化身为超级玛丽亚的你现身了，告诉他吧。。。。。。

## 输入 ##

首先输入一个n。表示有n组测试数据。

每组测试数据有两行。

第一行为字符串S1，长度不大于1000000。

第二行为字符串S2，长度不大于10000,并且长度不小于2。

## 输出 ##

输出S2在S1的位置。如果有多个位置，只输出第一个位置。

如果找不到，就输出“::>\_<::“（不输出双引号）。

## 示例输入 ##

1
    ASDFGDF
    DF

## 示例输出 ##

## 提示 ##

## 来源 ##

## 示例程序 ##

解法一：

#include<stdio.h>  
    #include<string.h>  
    int next[10010],n,m;  
    char b[10010],a[1000010];  
    void Next()  
    {  
        next[0]=-1;  
        for(int j=1;j<m;j++)  
        {  
            int i=next[j-1];  
            while(b[i+1]!=b[j]&&i>=0)  
            {  
                i=next[i];  
            }  
            if(b[i+1]==b[j])  
                next[j]=i+1;  
            else  
                next[j]=-1;  
        }  
    }  
    int KMP()  
    {  
        Next();  
        int p=0,s=0;  
        while(p<m&&s<n)  
        {  
            if(a[s]==b[p])  
            {  
                p++;  
                s++;  
            }  
            else  
            {  
                if(p==0)  
                    s++;  
                else  
                    p=next[p-1]+1;  
            }  
        }  
        if(p<m)  
            return -1;  
        else  
            return s-m+1;  
    }  
    int main()  
    {  
        int i,j,k,t;  
        scanf("%d",&t);  
        while(t--)  
        {  
            scanf("%s",a);  
            scanf("%s",b);  
            n=strlen(a);  
            m=strlen(b);  
            k=KMP();  
            if(k==-1)  
                printf("::>_<::\n");  
            else  
                printf("%d\n",k);  
        }  
    }

解法二：

#include<stdio.h>
    #include<string.h>
    char a[1000010],b[10010];
    int next[10010],n,m;
    void get_next(char T[],int next[])
    {
        int i=0;
        next[0]=-1;
        int j=-1;
        while(i<m-1)
        {
            if(j==-1||T[i]==T[j])
            {
                i++;
                j++;
                next[i]=j;
            }
            else
                j=next[j];
        }
    }
    int Index_KMP(char S[],char T[])
    {
        int i=0,j=0;
        while(i<n&&j<m)
        {
         if(j==-1||S[i]==T[j])
         {
             i++;
             j++;
         }
         else
            j=next[j];
        }
        if(j>=m)
            return i-m+1;
        else
            return 0;
    }
    int main()
    {
        int i,j,k,t;
        scanf("%d",&t);
        getchar();
        while(t--)
        {
          scanf("%s",a);
          scanf("%s",b);
           n=strlen(a);
           m=strlen(b);
           get_next(b,next);
           k=Index_KMP(a,b);
           if(k!=0)
            printf("%d\n",k);
            else
                printf("::>_<::\n");
        }
    }

解法二（改进）

#include<stdio.h>
    #include<string.h>
    char a[1000010],b[10010];
    int nextval[10010],n,m;
    void get_nextval(char T[],int nextval[])
    {
     int i=0;
        nextval[0]=-1;
        int j=-1;
        while(i<m-1)
        {
            if(j==-1||T[i]==T[j])
            {
                i++;
                j++;
                if(T[i]!=T[j])
                    nextval[i]=j;
                else
                nextval[i]=nextval[j];
            }
            else
                j=nextval[j];
        }
    }
    int Index_KMP(char S[],char T[])
    {
        int i=0,j=0;
        while(i<n&&j<m)
        {
         if(j==-1||S[i]==T[j])
         {
             i++;
             j++;
         }
         else
            j=nextval[j];
        }
        if(j>=m)
            return i-m+1;
        else
            return 0;
    }
    int main()
    {
        int i,j,k,t;
        scanf("%d",&t);
        getchar();
        while(t--)
        {
          scanf("%s",a);
          scanf("%s",b);
           n=strlen(a);
           m=strlen(b);
           get_nextval(b,nextval);
           k=Index_KMP(a,b);
           if(k!=0)
            printf("%d\n",k);
            else
                printf("::>_<::\n");
        }
    }