Cod sursa(job #1166283)

Utilizator StefansebiStefan Sebastian Stefansebi Data 3 aprilie 2014 13:47:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, t;
queue <int> q;
int m, n, i, k, j, v[2000000];

int main(){
    fin >> p >> t;
    p.insert(0, " ");
    t.insert(0, " ");
    m = p.length() - 1;
    n = t.length() - 1;
    for (i = 2; i <= m; i++){
        while (p[k + 1] != p[i] and k > 0)
            k = v[k];
        if (p[k + 1] == p[i]){
            k++;
            v[i] = k;
        }
    }
    j = 1; i = 0;
    while (j <= n){
        if (p[i + 1] == t[j]){
            i++;
            j++;
            if (i == m)
                q.push(j - i - 1);//fout << j - i - 1 << " ";
        }
        else if (i > 0)
            i = v[i];
        else
            j++;
    }
    fout << q.size() << '\n';
    i = 1;
    while (!q.empty() and i <= 1000){
        fout << q.front() << " ";
        q.pop(); i++;
    }
    fout << '\n';
    fin.close();
    fout.close();
}