Cod sursa(job #632327)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 10 noiembrie 2011 21:17:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <string>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string a,b;
int n,m,i,j,k,pi[2000001],q,sol[2000001];

int main() {
    f >> a;f >> b;
    n=a.size();m=b.size();
    a=' '+a;b=' '+b;
    k=0;pi[1]=0;
    for (i=2;i<=n;i++) {
        while (k>0 && a[k+1]!=a[i])
            k=pi[k];
        if (a[k+1]==a[i])
            k++;
        pi[i]=k;
    }
    q=0;
    for (i=1;i<=m && sol[0]<1000;i++) {
        while (q>0 && a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            q++;
        if (q==n) {
            sol[++sol[0]]=i-n;
            q=pi[n];
        }
    }
    g << sol[0] << '\n';
    for (i=1;i<=sol[0];i++)
        g << sol[i] << ' ';
    f.close();g.close();
    return 0;
}