Cod sursa(job #3264279)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 19 decembrie 2024 23:30:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

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

string s,s1;
int p[2000001];
vector<int> rasp;

void prec(){
    int lung=0,i;
    p[0]=0;
    for(i=1;i<s.size();){
        if(s[i]==s[lung]){
            lung++;
            p[i]=lung;
            i++;
        }else if(lung!=0){
            lung=p[lung-1];
        }else{
            p[i]=0;
            i++;
        }
    }
}

void kmp(){
    int i,j;
    i=j=0;
    while(i<s1.size()){
        if(s1[i]==s[j]){
            i++;j++;
            if(j==s.size()){
                rasp.push_back(i-j);
                j=p[j-1];
            }
        }else if(j!=0) j=p[j-1];
        else i++;
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i;
    cin>>s>>s1;
    prec();
    kmp();
    cout<<rasp.size()<<"\n";
    for(i=0;i<min((int)rasp.size(),1000);i++){
        cout<<rasp[i]<<" ";
    }
    return 0;
}