Cod sursa(job #876860)

Utilizator paiePopescu Andreea paie Data 12 februarie 2013 11:19:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <string>
using namespace std;

int main ()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    string a,f;
    int t[2000000],i,j,n,m,k[100000],h=0;
    getline(in,a);
    getline(in,f);
    a.insert(0,"0");
    f.insert(0,"0");
    n=a.size();
    m=f.size();
    j=0;
    t[1]=0;
    //out<<a<<endl<<f<<endl;
    for(i=2;i<=n;i++){
        while(j>0&&a[j+1]!=a[i])
            j=t[j];
        if(a[j+1]==a[i])
            j++;
        t[i]=j;}
    j=0;
//    for(i=0;i<n;i++)
  //      out<<t[i]<<' ';

    for(i=0;i<=m;i++){
        while(j>0&&a[j+1]!=f[i])
            j=t[j];
        if(a[j+1]==f[i])
            j++;
        if(j==n-1){
            k[h++]=i-n+1;}}
    out<<h<<'\n';
    for(i=0;i<h;i++)
        out<<k[i]<<' ';
    out<<'\n';
    return 0;
}