# 题解0012：剪花布条（KMP）(Question 0012: cut cloth strip (KMP))-其他

## 题解0012：剪花布条（KMP）(Question 0012: cut cloth strip (KMP))

``````#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;
}
}
}``````

``````#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 >

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;
}
}
} ``````