Cod sursa(job #1781590)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 17 octombrie 2016 00:17:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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;
char a[2000001],b[2000001];
vector<int> positions;

int main()
{
    
    fin >> (a+1);
    n = strlen(a+1);
    fin >> (b+1);
    m = strlen(b+1);
    
    k=0;
    for(i=2; i <= n; ++i)
    {
        while (k && a[k+1] != a[i])
            k = dinamicaA[k];
        
        if (a[k+1] == a[i])
            ++k;
        
        dinamicaA[i] = k;
    }
    
    k = 0; k2 = 0;
    for (i=1; i <= m; ++i)
    {
        while (b[i] != a[k+1] && k)
            k = dinamicaA[k];
        
        if (b[i] == a[k+1])
        {
            ++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 << " ";
    
    return 0;
}