Cod sursa(job #1781587)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 17 octombrie 2016 00:00:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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];
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;
    for (i=0; i < m; ++i)
    {
        while (b[i] != a[k] && k)
        {
            k = dinamicaA[k-1];
        }
        if (b[i] == a[k])
        {
            ++k;
            if(k==a.size())
                positions.push_back(i);
        }
        dinamicaB[i] = k;
    }
    
    n = positions.size();
    fout << positions.size() << "\n";
    
    for(i = 0; i < min(1000,n); ++i)
        fout << positions[i] - a.size() + 1 << " ";
    
    return 0;
}