Cod sursa(job #1629057)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 4 martie 2016 12:29:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

#define NMax 20000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[NMax],y[NMax];
vector<int> ANS;
int pi[NMax];
int X,Y;

void prefix(){
    int k = 0;
    pi[0] = 0;pi[1] = 0;
    X = strlen(x + 1);
    for(int i = 2; i <= X; ++i){
        while(k > 0 && x[k + 1] != x[i])
            k = pi[k];
        if(x[k + 1] == x[i])
            ++k;
        pi[i] = k;
    }
}
void potrivire(){
    int k = 0;
    X = strlen(x + 1); Y = strlen(y + 1);
    for(int i = 1; i <= Y; ++i){
        while(k > 0 && x[k + 1] != y[i])
            k = pi[k];
        if(x[k + 1] == y[i])
            ++k;
        if(k == X)
            ANS.push_back(i - X + 1);
    }
}
int main()
{
    f.getline(x + 1,NMax);
    f.getline(y + 1,NMax);
    prefix();
    potrivire();
    g << ANS.size()<<"\n";
    if(ANS.size() > 1000)
        w = 1000;
    else
        w = ANS.size();
    for(int i = 0; i < w; ++i){
        g << ANS[i] - 1 <<" ";
    }
    return 0;
}