Cod sursa(job #1833075)

Utilizator AndreiTACAndrei Cristian AndreiTAC Data 21 decembrie 2016 16:45:37
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string.h>

using namespace std;

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    char a[2000001],b[2000001];
    int urm[2000000],i,j,m,n,c=0,v[1000];
    in>>a>>b;
    m=strlen(a);
    n=strlen(b);
    urm[0]=-1;
    j=-1;
    for(i=1;i<m;i++)
        {
            while(j>-1 && a[j+1]!=a[i])
                {
                    j=urm[j];
                }
            if(a[j+1]==a[i])
                {
                    j++;
                }
            urm[i]=j;
        }
    j=-1;
    for(i=0;i<n;i++)
        {
            while(j>-1 && a[j+1]!=b[i])
                {
                    j=urm[j];
                }
            if(a[j+1]==b[i])
                {
                    j++;
                }
            if(j==m-1)
                {
                    if(c<1000)
                        v[c]=i-m+1;
                    c++;
                }
        }
    out<<c<<"\n";
    for(i=0;i<c;i++)
        {
            out<<v[i]<<" ";
        }
    return 0;
}