Cod sursa(job #1153118)

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

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