CSU 1598 最长公共前缀 KMP连续匹配

Problem D: 最长公共前缀

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 63  Solved: 52

[Submit][Status][Web Board]

Description

给定两个字符串s和t，现有一个扫描器，从s的最左边开始向右扫描，每次扫描到一个t就把这一段删除，输出能发现t的个数。

Input

第一行包含一个整数T（T<=50），表示数据组数。

每组数据第一行包含一个字符串s，第二行一个字符串t，字符串长度不超过1000000。

Output

对于每组数据，输出答案。

Sample Input

2

ababab

ab

ababab

ba

Sample Output

3

2

HINT

 很裸的一道KMP的题目，不过这个是KMP的连续匹配，之前刚写过一个连续匹配的模板，正好用上，这里就再粘一遍

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <memory.h>
#define MAX 10000
using namespace std;
int C;
void getNext(char *str,int *next)
{
    int j=0,k=-1;//k指向串的前部分，j指向串的后部分
    next[0]=-1;//规定
    int len=strlen(str);
    while(j<len)//扫描串的每一个字符，求出它的next
    {
        if(k==-1||str[k]==str[j])//如果k为-1或者上一次匹配成功，则k，j指针向后移动
        {
            k++,j++;
            if(str[k]!=str[j])//优化，当这两个字符不相等的时候，那么回溯才是有意义的，因为如果相等回溯过去
            {
                next[j]=k;
            }
            else
            {
                next[j]=next[k];
            }
        }
        else
            k=next[k];//如果匹配失败，k回溯到上一个匹配成功的k的下一个位置，因为j向前走了一个位置
    }
}


void KMP(char *m_str,char *str)
{
    int next[MAX];
    getNext(str,next);
    int i=0,j=0;//i主串指针，j模式串指针
    int m_len,len;
    m_len=strlen(m_str);
    len=strlen(str);
    while(i<=m_len)//之所以取到m_len，是因为可能最后一段匹配成功
    {
        if(i==m_len&&j<len)//最后一段如果不匹配，退出
            break;
        if(j>=len)//匹配成功后的处理
        {
            C++;
           // cout<<i-j<<endl;//输出匹配成功的位置
            //因为i，j都多走了一步，所以i不用动，j回退到起点
            j=0;

        }
        else if((j==-1||m_str[i]==str[j])&&i<m_len)
        {
            i++;
            j++;
        }
        else if(i<m_len)
            j=next[j];//匹配失败回溯
    }


}


int main()
{

    char m_str[MAX],str[MAX];
    int t;
    cin>>t;
    while(t--)
    {cin>>m_str>>str;
    C=0;
        KMP(m_str,str);
        cout<<C<<endl;
    }
    return 0;
}