Cod sursa(job #2471518)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 11 octombrie 2019 07:51:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2e6+4;

string a,b;
long long sol,lps[NMAX],sz,poz[1004],n;

void build(){
    int k;
    for(int i=1;i<=a.size();++i){
        k=lps[i-1];
        while(a[k]!=a[i]){
            if(!k){
                k=-1;
                break;
            }
            k=lps[k-1];
        }
        lps[i]=k+1;
        if(lps[i] == sz){
            ++sol;
            if(n<1000)
                poz[n++]=i-sz*2;
        }
    }
}

int main(){
    fin>>a>>b;
    sz=a.size();
    a=a+"#"+b;
    build();
    fout<<sol<<'\n';
    for(int i=0;i<n;++i)
        fout<<poz[i]<<' ';
    return 0;
}
///KMP