Cod sursa(job #1514671)

Utilizator ade_tomiEnache Adelina ade_tomi Data 31 octombrie 2015 13:48:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
int  p[2000005],sol[1003],i,j,n,m,x,kmp;
char s1[2000005],s2[2000005];
string ss1,ss2;
int main()
{

    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>ss1;
    cin>>ss2;
  //  pi[1]=-1;
    for(int i=0;i<ss1.size();i++)
    {

        n++;
        s1[n]=ss1[i];
    }
    for(int i=0;i<ss2.size();i++)
    {

        m++;
        s2[m]=ss2[i];

    }
    x=0;
    for(i=2;i<=n;i++)
    {


        while(x>0&&s1[x+1]!=s1[i])
            x=p[x];
        if(s1[x+1]==s1[i])
            x++;
        p[i]=x;
    }

    x=0;
    for(i=1;i<=m;i++)
    {
        while(kmp>0&&s1[kmp+1]!=s2[i])
            kmp=p[kmp];
        if(s1[kmp+1]==s2[i])
            kmp++;
        if(kmp==n)
        {

            sol[0]++;
            if(sol[0]<=1000)
                sol[sol[0]]=i-n;
        }
    }
    cout<<sol[0]<<"\n";
    for(i=1;i<=min(1000,sol[0]);i++)
        cout<<sol[i]<<" ";
    return 0;

}