Cod sursa(job #2755891)

Utilizator ViAlexVisan Alexandru ViAlex Data 28 mai 2021 18:00:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int mx=2e6+100;

string pat,tex;
int lps[mx];



void preprocess(){
    int i=0,j=1;
    lps[0]=0;
    while(j<pat.length()){
        if(pat[i]==pat[j]){
            i++;
            lps[j]=i;
            j++;
        }
        else{
            if(i==0){
                lps[j]=0;
                j++;
            }
            else{
                i=lps[i-1];
            }
        }
    }
}

void kmp(){
    vector<int> result;
    int i=0,j=0;
    while(j<tex.length()){
        if(pat[i]==tex[j]){
            i++;
            j++;
        }

        if(i==pat.length()){
            result.push_back(j-(int)pat.length());
            i=lps[i-1];
        }

        if(pat[i]!=tex[j]){
            if(i==0){
                j++;
            }
            else{
                i=lps[i-1];
            }
        }
    }

    out<<result.size()<<endl;
    int len=min((int) result.size(),1000);
    for(int p=0;p<len;p++){
        out<<result[p]<<" ";
    }


}


void solve(){
    in>>pat>>tex;
    preprocess();
    kmp();
}

int main(){
    solve();
    return 0;
}