Cod sursa(job #1781589)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 17 octombrie 2016 00:06:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
//
//  main.cpp
//  KMP
//
//  Created by Albastroiu Radu on 10/16/16.
//  Copyright © 2016 Albastroiu Radu. All rights reserved.
//

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cmath>

using namespace std;

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

int k, i, n, m, dinamicaA[2000001], dinamicaB[2000001], pozitii[2000001], k2;
string a,b;
vector<int> positions;

int main()
{
    
    fin >> a >> b;
    
    n = a.size();
    m = b.size();
    
    k=0;
    dinamicaA[0] = 0;
    for(i=1; i < n; ++i)
    {
        while (k && a[k] != a[i])
            k = dinamicaA[k];
        
        if (a[k] == a[i])
            ++k;
        
        dinamicaA[i] = k;
    }
    
    k = 0; k2 = 0;
    for (i=0; i < m; ++i)
    {
        while (b[i] != a[k] && k)
        {
            k = dinamicaA[k-1];
        }
        if (b[i] == a[k])
        {
            ++k;
            if(k==n)
                pozitii[++k2] = i;
        }
        dinamicaB[i] = k;
    }
    
    fout << k2 << "\n";
    k2 = min(1000,k2);
    for(i = 1; i <= k2; ++i)
        fout << pozitii[i] - n + 1 << " ";
    
    return 0;
}