Cod sursa(job #1819378)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 30 noiembrie 2016 16:01:18
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 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 <cstring>
#include <cmath>

using namespace std;

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

int main()
{
    string key_word, text, aux;
    aux = " ";
    
    fin >> key_word;
    fin >> text;
    
    key_word = aux + key_word;
    text = aux + text;
    
    auto n = key_word.size();
    auto m = text.size();
    
    int k = 0;
    int match_key_word[20];
    match_key_word[0] = 0;
    match_key_word[1] = 0;
    
    for(int i = 2; i < n; i++)
    {
        while(k && key_word[i] != key_word[k + 1])
            k = match_key_word[k];
        
        if(key_word[i] == key_word[k + 1])
            k++;
        
        match_key_word[i] = k;
    }
    
    k = 0;
    int match_text[20];
    match_text[0] = 0;
    vector<int> positions;
    
    for(int i = 1; i < m; i++)
    {
        while(k && text[i] != key_word[k + 1])
            k = match_key_word[k];
        
        if(text[i] == key_word[k + 1])
        {
            k++;
            if( k == n - 1 )
                positions.emplace_back(i - n + 1);
        }
    
        match_text[i] = k;
    }
    
    fout << positions.size() << "\n";
    
    int i = 0;
    while(i < 1000 && i < positions.size())
        fout << positions[i++] << " ";
    
    return 0;
}