题解0012:剪花布条(KMP)(Question 0012: cut cloth strip (KMP))

信奥一本通1465 KPM例题

题目链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1465

题目描述:给出花布条和小饰条(字符串),求花布条中能剪出几块小饰条。

先来一个暴力代码  (这题测试点是真氵,暴力竟然过了)

#include<bits/stdc++.h>
using namespace std;
int next[1001],i=0,j=0,we=0;
string a,b;
int main(){
    while(cin>>a){
        we=0;
        i=0;
        j=0;
        if(a=="#"){
            break;
        }
        else{
            cin>>b;
            int as=a.size();
            int bs=b.size();
            while(i<as){
                if(a[i]!=b[j]){
                    i=i-j+1;
                    j=0;
                }else{
                    i++;
                    j++;
                }
                if(j==bs){
                    we++;
                    j=0;
                }
            }
            cout<<we<<endl;
        }
    }
}

暴力自然不用多说,挨个比就行。匹配成功就接着往下匹配,失败就回去重新匹配。

但是,这种暴力法时间复杂度可高,遇到数据大的情况得全TLE。

那怎么办呢?

这就要介绍一种NB的算法——KMP算法。

这种算法是当子串与母串匹配不一样时,母串不动,计算出下一步子串移动的位置next [ j ],从而节省时间。

上代码:

#include<bits/stdc++.h>
using namespace std;
int nextl[1001]={0};//这个数组名不能直接用next,容易报错 
string a,b;
int KMP(){
    int i=0,j=0,we=0;
    int as=a.size(),bs=b.size();
    while(i<as){
        if(a[i]==b[j]||j==-1){//当单个字符匹配成功或前面没东西 
            i++;
            j++;//i,j都往前挪 
            if(j==bs){//字符串匹配成功 
                we++; 
                j=0;//子串归0 
            }
        }else{
            j=nextl[j];//上next数组,移动到下一个位置 
        }
    }
    return we;
}
void Next(){//计算next数组值 
    int bs=b.size();
    nextl[0]=-1;//代表前面没东西 
    int j=0,k=-1;
    while(j<bs){
        if(k==-1||b[j]==b[k]){//当前面没有东西或j、k对应的字符一样 
            nextl[j++]=k++;//直接往后挪一位,因为前几位字符=后几位字符或前面啥也没有 
        }else{
            k=nextl[k];
        }
    }
}
int main(){//不必多说了 
    while(cin>>a){
        if(a=="#"){
            break;
        }else{
            cin>>b;
            Next();
            cout<<KMP()<<endl;
        }
    }
} 
————————

Xinao yibentong 1465 < strong > KPM example < / strong >

题目链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1465

Title Description: give the flower cloth strip and small decoration strip (string), and find out how many small decoration strips can be cut out of the flower cloth strip.

Let’s start with a violence code (the test point of this question is true, but the violence passed)

#include<bits/stdc++.h>
using namespace std;
int next[1001],i=0,j=0,we=0;
string a,b;
int main(){
    while(cin>>a){
        we=0;
        i=0;
        j=0;
        if(a=="#"){
            break;
        }
        else{
            cin>>b;
            int as=a.size();
            int bs=b.size();
            while(i<as){
                if(a[i]!=b[j]){
                    i=i-j+1;
                    j=0;
                }else{
                    i++;
                    j++;
                }
                if(j==bs){
                    we++;
                    j=0;
                }
            }
            cout<<we<<endl;
        }
    }
}

Naturally, there is no need to say more about violence. Just compare one by one. If the match is successful, then go down to match, and if it fails, go back to match again.

However, the time complexity of this violence method can be high. In case of large data, we have to use full TLE.

Then what shall I do?

This is to introduce an NB algorithm – < strong > KMP algorithm

This algorithm is to calculate the position next [J] of the substring movement in the next step when the substring matches differently from the parent string, so as to save time.

Upper Code:

#include<bits/stdc++.h>
using namespace std;
int nextl[1001]={0};//这个数组名不能直接用next,容易报错 
string a,b;
int KMP(){
    int i=0,j=0,we=0;
    int as=a.size(),bs=b.size();
    while(i<as){
        if(a[i]==b[j]||j==-1){//当单个字符匹配成功或前面没东西 
            i++;
            j++;//i,j都往前挪 
            if(j==bs){//字符串匹配成功 
                we++; 
                j=0;//子串归0 
            }
        }else{
            j=nextl[j];//上next数组,移动到下一个位置 
        }
    }
    return we;
}
void Next(){//计算next数组值 
    int bs=b.size();
    nextl[0]=-1;//代表前面没东西 
    int j=0,k=-1;
    while(j<bs){
        if(k==-1||b[j]==b[k]){//当前面没有东西或j、k对应的字符一样 
            nextl[j++]=k++;//直接往后挪一位,因为前几位字符=后几位字符或前面啥也没有 
        }else{
            k=nextl[k];
        }
    }
}
int main(){//不必多说了 
    while(cin>>a){
        if(a=="#"){
            break;
        }else{
            cin>>b;
            Next();
            cout<<KMP()<<endl;
        }
    }
}