Cod sursa(job #3247103)

Utilizator serbanbBrindescu Serban serbanb Data 5 octombrie 2024 17:12:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>

using namespace std;

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

int Z[4000005];
string A,B,concat;

void buildZ()
{
    int nrMatches=0;
    concat=A+"*"+B;
    int st=0,dr=0;
    for(int i=1;i<concat.length();++i){
        if(i>dr){
            st=i;
            dr=i;
            while(concat[dr]==concat[dr-st]&&dr<concat.length()){
                dr++;
            }
            Z[i]=dr-st;
            dr--;
        }
        else{
            int k=i-st;
            if(Z[k]<dr-i+1){
                Z[i]=Z[k];
            }
            else{
                st=i;
                while(dr<concat.length() && concat[dr]==concat[dr-st]){
                    dr++;
                }
                Z[i]=dr-st;
                dr--;
            }
        }
        if(Z[i]==A.length()){
            nrMatches++;
        }
    }
    fout << nrMatches << '\n';
}

void findMatches()
{
    int cnt=0;
    for(int i=1;i<concat.length();++i){
        if(Z[i]==A.length()){
            cnt++;
            if(cnt<=1000){
                fout << i-A.length()-1 << ' ';
            }
            else{
                break;
            }
        }
    }
}

int main()
{
    fin >> A >> B;
    buildZ();
    findMatches();
    return 0;
}