hdoj 1686 Oulipo【kmp】

水深无声 2022-08-04 12:37 134阅读 0赞

# Oulipo #

**Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 7753    Accepted Submission(s): 3122**

题目大意：给个数 T，表示有T组测试数据；

每个测试用例给两个字符串，第一个字符串的长度L1（1 ≤ |L1| ≤ 10,000），第二个字符串长度L2（1 ≤ |L2| ≤ 1,000,000）

求第一个字符串在第二个字符串中出现的次数，如下例：

Sample Input

3
    BAPC
    BAPC
    AZA
    AZAZAZA
    VERDI
    AVERDXIVYERDIAN

Sample Output

1
    3
    0

此处先设字符串一为str，字符串二位buf；

传统思路：用str首字符与buf首字符比较，两种情况，如下

①如果从str首字符一直比到str尾字符都一样，则计数器+1，然后将str首字符移至buf第二个字符

②如果从str首字符开始比，中途有一个不匹配，则str首字符向buf的下一个字符移动，

重复上述两个动作，直到str首位移至buf的L2-L1-1位为止；

kmp思路：先求出第一个字符串的匹配表（若不会求看这篇 [ http://blog.csdn.net/nailnehc/article/details/47402529][http_blog.csdn.net_nailnehc_article_details_47402529]），然后就可以进行比较了，然后就没有然后来，直接记录出现次数，然后输出，（模板题真难写思路啊，[http://www.cnblogs.com/goagent/archive/2013/05/16/3068442.html][http_www.cnblogs.com_goagent_archive_2013_05_16_3068442.html]可以去看看这）

已Accept代码（用c提交）

<table style="border-bottom:#879bff 1px dashed; width:623px; height:25px"> 
 <tbody> 
  <tr> 
   <td><span style="background-color:#999999">Exe.Time</span></td> 
   <td><span style="background-color:#999999">Exe.Memory</span></td> 
   <td><span style="background-color:#999999">Code Len.</span></td> 
   <td><span style="background-color:#999999">Language</span></td> 
  </tr> 
 </tbody> 
</table>

#include<stdio.h>
    #include<string.h>
    int p[10001];
    int len1,len2,total;
    char str[10001],buf[1000001];
    void getp(){
        int i=0,j=-1;
        p[0]=-1;
        while(i!=len1){
            if(j==-1||str[i]==str[j]){
                p[++i]=++j;
                p[i]=str[i]!=str[j]?j:p[j];		//优化，可以看给你们提供的第二个博客的第五部分
            }
                
            else
                j=p[j];
        }
    }
    
    void kmp(){
        int i=0,j=0;
        while(i!=len2){
            if(j==-1||buf[i]==str[j])
                ++i,++j;
            else
                j=p[j];
            if(j==len1){
                total++;
                j=p[j];
            }
        }
    }
    
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%s%s",str,buf);
            len1=strlen(str);
            len2=strlen(buf);
            total=0;
            getp();
            kmp();
            printf("%d\n",total);
        }
        return 0;
    }

[http_blog.csdn.net_nailnehc_article_details_47402529]: http://blog.csdn.net/nailnehc/article/details/47402529
[http_www.cnblogs.com_goagent_archive_2013_05_16_3068442.html]: http://www.cnblogs.com/goagent/archive/2013/05/16/3068442.html