Cod sursa(job #2251438)

Utilizator gabriel-mocioacaGabriel Mocioaca gabriel-mocioaca Data 1 octombrie 2018 17:05:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

#define cout out
#define cin in

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

vector<int> make_pattern(string pattern){
    vector<int> pat;
    int n = pattern.size();
    pat.resize(n, 0);

    int j = 0, i = 1;
    while (i < n){
        if(pattern[i] == pattern[j]){
            pat[i] = j + 1;
            i++; j++;
        }else{
            if(j != 0){
                j = pat[j - 1];
            }else{
                i++;
            }
        }
    }

    return pat;
}

int main(){
    string pattern, text;
    int n, m;
    int i, j;
    int cnt = 0;

    cin >> pattern >> text;
    n = pattern.size();
    m = text.size();
    vector<int> pat;
    vector<int> sol;
    pat = make_pattern(pattern);

    i = j = 0;

    while(i < m){
        if(text[i] == pattern[j]){
            if(j == n - 1){
                cnt++;
                sol.push_back(i - n + 1);
                j = pat[j];
            }else{
                j++;
            }
            i++;
        }else{
            if(j != 0){
                j = pat[j - 1];
            }else{
                i++;
            }
        }
    }

    cout << cnt << '\n';
    if(cnt){
        int t = min(cnt, 1000);
        for(int it = 0; it < t; ++it)
            cout << sol[it] << ' ';
    }
    return 0;
}