Cod sursa(job #1974980)

Utilizator danalex97Dan H Alexandru danalex97 Data 29 aprilie 2017 17:04:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
//#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

string t, p;
int n, m, tot;
vector<int> ans;

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

int main()
{
    cin >> p >> t;
    n = t.size();
    m = p.size();
    t.insert(0, "#");
    p.insert(0, "#");
    
    vector<int> pref(m + 1);
    
    pref[0] = pref[1] = 0;
    for (int i = 2; i <= m; ++i) {
        int pos = pref[i - 1];
        while (p[pos + 1] != p[i] && pos > 0) {
            pos = pref[pos];
        }
        pref[i] = pos + int(p[pos + 1] == p[i]);
    }
    
    // for (int i = 1; i <= m; ++i) {
    //     cout << pref[i] << ' '; 
    // }
    // cout << '\n';
    
    int i = 0, j = 0;
    while (i < n) {
        while (t[i + 1] != p[j + 1] && j > 0) {
            j = pref[j];
        }
        j += int(p[j + 1] == t[i + 1]);
        if (j == m) {
            if (tot < 1000) {
                ans.push_back(i);
            }
            tot++;
        }
        ++i;
    }
    
    cout << tot << '\n';
    for (auto x : ans) {
        cout << x << ' ';
    }
    cout << '\n';
}