Cod sursa(job #2001310)

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

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

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;
}


template<typename T>
void printVec(vector<T> vec) {
    for (auto x: vec) {
        fout << x << ' ';
    }
}

int main() {
    string pat, tex;
    // string tex = "ABAABACABADABACABACABADAA";
    // string pat = "ABACABADABACABACABAD";
    fin >> pat >> tex;
    // ABA
    // CABBCABABAB
    
    vector<int> v = 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 = v[p - 1];
        
        if (tex[i] == pat[p]) p += 1;
        
        if (p == pat.length()) {
            ans.push_back(i - pat.length() + 1);
            p = v[p - 1];
        }
    }
    
    fout << ans.size() << '\n';
    printVec(ans);
    
    return 0;
}