Cod sursa(job #2794792)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 5 noiembrie 2021 13:55:51
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#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 main (){
    fin>>a>>b;


    ///precalc longest prefix sufix
    int p=1, len=0; lps[0] = 0;
    while(p < a.size()){
        if(a[p] == a[len])
            lps[p++] = ++len;
        else{
            if(len != 0)
                len = lps[len-1];
            else
                lps[++p] = 0;
        }
    }

    int i=0, j=0;
    while(i < b.size()){
        if(a[j] == b[i]){
            i++;
            j++;
        }else{

            if(j == a.size())
                sol.push_back(i-j), j=lps[j-1];
            else if(i < b.size() && b[i] != a[j]){

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

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