Cod sursa(job #2313566)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 7 ianuarie 2019 09:19:57
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

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

istream & in = fin;
ostream & out = fout;

string pat, tgt;
int pre[2000041];

int numba = 0;
int numbas[1041];
void Read()
{
    getline(in, pat);
    getline(in, tgt);
}

void CalcPre()
{
    int i = 1, j = 0;
    while(i < pat.size()){
        if(pat[i] == pat[j]){
            pre[i] = j+1;
            i++;j++;
        }else{
            if(j != 0){
                j = pre[j-1];
            }else{
                pre[i] = 0;
                i++;
            }
        }
    }
}

void KMP()
{
    int i = 0, j = 0;
    while(i < tgt.size()){
        while(j != 0 && tgt[i] != pat[j]){
            j = pre[j];
        }
        if(tgt[i] == pat[j]){
            j++;
        }
        i++;
        if(j == pat.size()){
            j = pre[j-1];
            if(numba < 1000){
                numbas[numba] = i-pat.size();
            }
            numba++;
        }
    }
}

void Solve()
{
    CalcPre();
    KMP();
}

void Write()
{
    out << numba << "\n";
    numba = min(numba, 1000);
    for(int i = 0; i < numba; i++){
        out << numbas[i] << " ";
    }
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}