Cod sursa(job #2288905)

Utilizator KemyKoTeo Virghi KemyKo Data 24 noiembrie 2018 09:23:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000002
 
using namespace std;
 
ifstream f("strmatch.in");
ofstream g("strmatch.out");
 
int n, m;
int T[NMAX];
char a[NMAX], b[NMAX];
vector <int> rez;
 
void prefix()
{
    int k = 0, i;
 
    for(i=2; i<=n; ++i) {
        while(k > 0 && a[k + 1] != a[i])
            k = T[k];
        if(a[k + 1] == a[i])
            ++k;
        T[i] = k;
    }
}
 
void KMP()
{
    int k = 0, i;
 
    for(i=1;i<=m;++i){
        while(k>0 && a[k + 1] != b[i])
            k = T[k];
        if(a[k + 1] == b[i])
            ++k;
        if(k==n){
            rez.push_back(i - n);
            k=T[k];
        }
    }
}
 
void afis()
{
    int i, sz = rez.size();
 
    g<<sz<<'\n';
    for(i=0;i<rez.size() && i<1000;++i)
        g<<rez[i]<<' ';
}
 
int main()
{
    f.getline(a + 1, NMAX); //citire
    f.getline(b + 1, NMAX);
    n = strlen(a + 1);      //dimensiuni
    m = strlen(b + 1);
 
    if(n>m) {
        g<<'0';
        return 0;
    }
 
    prefix();           //precalc
    KMP();              //Search
 
    afis();
    return 0;
}