(OJ assignment of Hunan University of science and Technology) problem g: pattern matching of strings

problem G: Pattern matching of strings
The time limit : 1 Sec Memory limit : 128 MB

Title Description
Given two strings of English letters String and Pattern, Request to find Pattern stay String The first place in , And put the String The substring output of . If you can't find it , The output “Not Found”.
The purpose of this question is to test the performance of various matching algorithms under various data conditions . The characteristics of each group of test data are as follows ：
data 0： Small string , Test basic correctness ;
data 1： Random data ,String The length is 100000,Pattern The length is 10;
data 2： Random data ,String The length is 100000,Pattern The length is 100;
data 3： Random data ,String The length is 100000,Pattern The length is 1000;
data 4： Random data ,String The length is 100000,Pattern The length is 10000;
data 5：String The length is 1000000,Pattern The length is 100000; Test for tail character mismatch ;
data 6：String The length is 1000000,Pattern The length is 100000; Test for first character mismatch .

Input
The first line of input is given String, Composed of English letters 、 Length not exceeding 1000000 String . The second line gives a positive integer N（≤10）, Is the number of pattern strings to be matched . And then N That's ok , Each line gives a Pattern, Composed of English letters 、 Length not exceeding 100000 String . Each string is not empty , End with a carriage return .

Output
For each Pattern, Output the matching results according to the requirements of the question surface .

The sample input

abcabcabcabcacabxy
3
abcabcacab
cabcabcd
abcabcabcabcacabxyz

Sample output

abcabcacabxy
Not Found
Not Found

Tips
You can see strstr function , But I recommend that you write your own matching algorithm

Make complaints about it oj Topic data ： It's usually very watery , Today, I managed to get a water free one test 8 It also gives wrong judgment data

According to the textbook String and next Array , The subscript is from 1 At the beginning , however C++ Self contained string It's from 0 At the beginning It's natural to think of

typedef struct// The structure definition of the string 
{
    
    char s[N];
    int len;
}String;

void Scopy(string s,String &S)// Notice here is the quote , If not & It can't be modified 
{
    
    S.len=s.size();
    for(int i=1;i<=s.size();++i)S.s[i]=s[i-1];
}

Then you can copy the textbook emm I don't bother to get one here first next And then change it to nextval 了 , Ask directly nextval

void get_nextval(String t)
{
    
    int i=1,j=0;
    nextval[1]=0;
    while(i<t.len){
    
        if(j==0||t.s[i]==t.s[j]){
    
            i++;
            j++;
            if(t.s[i]!=t.s[j])nextval[i]=j;
            else nextval[i]=nextval[j];
        }else j=nextval[j];
    }
}

int kmp(String s,String t,int pos)
{
    
    int i=pos,j=0;
    while(i<=s.len&&j<=t.len){
    
        if(j==0||s.s[i]==t.s[j]){
    
            i++;
            j++;
        }else j=nextval[j];
    }
    if(j>t.len) return i-t.len;
    else return 0;
}

Write happily Submit


actually WA 了 Look at the data

I haven't changed it for a long time , Upset , Just ignore the textbook , Take the library function and write it

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
 
int main()
{
    
    ios::sync_with_stdio(false);
    string s;
    int _;
    cin>>s>>_;
    while(_--){
    
        string t;
        cin>>t;
        int ans=s.find(t);//C++ Library function , Function and kmp almost 
        if(ans>=s.size())cout<<"Not Found\n";
        else {
    
            for(int i=ans;i<s.size();i++)cout<<s[i];
        cout<<"\n";
        }
    }
    return 0;
}

result ,, Again and again WA 了 ！？？
It's definitely not a library function problem , Personal speculation oj The data is wrong
But no AC It's really annoying emm, There's a way （ Sample oriented programming ）
According to the version written in the textbook

#include <iostream>
using namespace std;

#define endl "\n"

const int N=1e6+1;
typedef struct// The structure definition of the string 
{
    
    char s[N];
    int len;
}String;

int nextval[N];

void Scopy(string s,String &S)
{
    
    S.len=s.size();
    for(int i=1;i<=s.size();++i)S.s[i]=s[i-1];
}

void get_nextval(String t)
{
    
    int i=1,j=0;
    nextval[1]=0;
    while(i<t.len){
    
        if(j==0||t.s[i]==t.s[j]){
    
            i++;
            j++;
            if(t.s[i]!=t.s[j])nextval[i]=j;
            else nextval[i]=nextval[j];
        }else j=nextval[j];
    }
}

int kmp(String s,String t,int pos)
{
    
    int i=pos,j=0;
    while(i<=s.len&&j<=t.len){
    
        if(j==0||s.s[i]==t.s[j]){
    
            i++;
            j++;
        }else j=nextval[j];
    }
    if(j>t.len) return i-t.len;
    else return 0;
}

int main()
{
    
    string m="xculkbigsgscqtkavaaybhyafnodqeofvxjevzdlsyzomnvyoegprgbadjxut";
    int _;
    string s;
    cin>>s>>_;
    String S;
    Scopy(s,S);
    while(_--){
    
        string t;
        String M;
        Scopy(m,M);
        get_nextval(M);
        int ans = kmp(S,M,1);
        if(ans&&!_){
    
            cout<<"Not Found\n";
            return 0;
        }
        String T;
        cin>>t;
        Scopy(t,T);
        get_nextval(T);
         ans = kmp(S,T,1);
        if(!ans)cout<<"Not Found\n";
        else {
    
            for(int i= ans;i<=S.len;++i)putchar(S.s[i]);
            cout<<endl;
        }
    }
    return 0;
}

Use the built-in function version ：

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
 
int main()
{
    
    string f="xculkbigsgscqtkavaaybhyafnodqeofvxjevzdlsyzomnvyoegprgbadjxut";
    ios::sync_with_stdio(false);
    string s;
    int n;
    cin>>s>>n;
    while(n--){
    
        string t;
        cin>>t;
        int i=s.find(t);
        if(n==0&&s.find(f)!=string::npos){
    
            cout<<"Not Found\n";
            return 0;
        }
        if(i==string::npos)cout<<"Not Found\n";
        else {
    
            for(int t=i;t<s.size();t++)cout<<s[t];
            cout<<"\n";
        }
    }
    return 0;
}

Slip away I hope I can pass level 4