Cod sursa(job #2001313)

Utilizator richieYRichie Yeung richieY Data 16 iulie 2017 13:41:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;

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

vector<int> pi(const 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;
    fin >> pat >> tex;
    
    vector<int> prefix = pi(pat);
    vector<int> ans;
    
    int p = 0;
    
    int n = tex.length();
    
    for (int i = 0; i < n; i += 1) {
        while (p > 0 && tex[i] != pat[p]) p = prefix[p - 1];
        
        if (tex[i] == pat[p]) p += 1;
        
        if (p == pat.length()) {
            ans.push_back(i - pat.length() + 1);
            p = prefix[p - 1];
        }
    }
    
    fout << ans.size() << '\n';
    for (int i = 0, to = min(ans.size(), 1000); i < to; i += 1) {
        fout << ans[i] << ' ';
    }
    
    return 0;
}