Cod sursa(job #2753370)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 22 mai 2021 17:06:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <cstring>
#include <vector>
#define K 2000002
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int prefix[K],n,m,i,j,x;
char a[K],b[K];
vector <int> sol;
int main(){
    fin>>a>>b;
    n=strlen(a);
    m=strlen(b);
    prefix[0]=0;
    //prefix[i]=lungimea celui mai lung prefix propriu care e si sufix in sirul s[0,..,i]
    for(i=1;i<n;i++){
        j=prefix[i-1];
        while(j>0 && a[i]!=a[j])
            j=prefix[j-1];
        if(a[i]==a[j])
            j++;
        prefix[i]=j;
    }
    int j=0;
    for(int i=0;i<m;i++){
        while(j>0 && b[i]!=a[j])
            j=prefix[j-1];
        if(b[i]==a[j])
            j++;
        if(j==n){
            j=prefix[j-1];
            sol.push_back(i-n+1);
        }
    }
    fout<<sol.size()<<"\n";
    for(int i=0;i<sol.size() && i<1000;i++)
        fout<<sol[i]<<" ";
    return 0;
}