Cod sursa(job #2153915)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 6 martie 2018 16:09:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define DIM 2000002

using namespace std;

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

int n,m, p[DIM], sol[DIM], nr;

char sir1[DIM], sir2[DIM];

void kmp(){
    p[1] = 0;
    int l = 0;
    for(int i = 2; i <= m; ++ i){
        while(sir1[i] != sir1[l + 1] && l != 0)
            l = p[l];
        
        if(sir1[i] == sir1[l + 1])
            ++ l;
        
        p[i] = l;
    }
    
    l = 0;
    
    for(int i = 1; i <= n; ++ i){
        while(sir2[i] != sir1[l + 1] && l != 0)
            l = p[l];
        
        if(sir2[i] == sir1[l + 1])
            ++ l;
        
        if(l == m){
            ++ nr;
            if(nr <= 1000)
                sol[nr] = i - m;
            l = p[l];
        }
    }
}

int main(int argc, const char * argv[]) {
    in>>sir1 + 1>>sir2 + 1;
    m = strlen(sir1 + 1);
    n = strlen(sir2 + 1);
    
    kmp();
    
    out<<nr<<'\n';
    
    nr = min(nr, 1000);
    
    for(int i = 1; i <= nr; ++ i)
        out<<sol[i]<<" ";
    
    return 0;
}