Cod sursa(job #2135823)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 19 februarie 2018 11:48:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2000005;
char a[nmax], b[nmax];
int n, m, urm[nmax];
vector<int> sol;

int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    fin >> a >> b;
    n = strlen(a);
    m = strlen(b);
    int k = -1;
    for (int i = 1; i < n; ++i){
        while(k > 0 && a[k+1] != a[i])
            k = urm[k];
        if(a[k+1] == a[i])
            ++k;
        urm[i] = k;
    }
    k = -1;
    for (int j = 0; j < m; ++j){
        while(k > 0 && a[k+1] != b[j])
            k = urm[k];
        if(a[k+1] == b[j])
            ++k;
        if(k == n-1){
            sol.push_back(j-n+1);
            k = urm[k];
        }
    }
    fout << sol.size() << "\n";
    for (vector<int>::iterator it = sol.begin(); it != sol.end(); ++it)
        fout << *it << " ";
    return 0;
}