Cod sursa(job #2001262)

Utilizator richieYRichie Yeung richieY Data 16 iulie 2017 03:44:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

vector<int> pi(string p) {
    int n = p.length();
    vector<int> res(n);
    
    res[0] = 0;
    int l = 0;
    
    for (int i = 1; i < n; i += 1) {
        while (l > 0 && p[i] != p[l]) l = res[l - 1];
        if (p[i] == p[l]) l += 1;
        res[i] = l;
    }
    return res;
}

int main() {
    string pat, tex;
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> pat >> tex;

    vector<int> v = pi(pat);
    vector<int> ans;
    
    int p = 0;
    int i_old = 0;
    for (int i = 0; i < (int)tex.length(); i++) {
        if (tex[i] == pat[p]) {
            if (p == (int)pat.length()-1) {
               ans.push_back(i_old);
               p = v[p-1];
                i = i_old + p;
                i_old = i+1;
            } else {
                p++;
            }
        } else {
            p = v[p-1];
            i = i_old + p;
            i_old = i+1;
        }
        
        if (p == (int)pat.length()) {
            ans.push_back(i_old);
            p = v[p];
            i = i_old + p;
            i_old = i+1;
        }
    }
    
    fout << ans.size() << endl;
    for (auto x: ans) {
        fout << x << ' ';
    }
    fout << endl;
    return 0;
}