Cod sursa(job #2794835)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 5 noiembrie 2021 15:24:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
///Solutie - KMP

#include <bits/stdc++.h>

using namespace std;

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

const int LIM = 2000005;

vector <int> sol;
int lps[LIM];
string a, b;
int na, nb;

int main (){
    fin>>a; na = a.size(); a = " " + a;
    fin>>b; nb = b.size(); b = " " + b;
    if(na > nb){fout<<0; return 0;}


    lps[0]=0;
    for(int i=2, len=0; i <= na; i++){

        while(len != 0 && a[i] != a[len+1])
            len = lps[len];

        if(a[i] == a[len+1])
            len++;

        lps[i] = len;
    }


    for(int i=1, len=0; i <= nb; i++){

        while(len != 0 && b[i] != a[len+1])
            len = lps[len];

        if(b[i] == a[len+1])
            len++;

        if(len == na)
            sol.push_back(i-na);

    }

    fout<<sol.size()<<"\n"; int go = min(1000, (int)sol.size());
    for(int i=0; i<go; i++)
        fout<<sol[i]<<" ";
    return 0;
}