Cod sursa(job #1832023)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 19 decembrie 2016 12:10:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//char sub[2000001],str[2000001];
string sub,str;
int pattern[2000001],n,m,rez[2000001];
int counter=0;
void makePattern()
{
    for(int i=1,j=0;i<n;i++)
    {
        while(sub[i]!=sub[j] && j>0)
            j=pattern[j-1];
        if(sub[i]==sub[j])
            pattern[i]=++j;
    }
}

void searchPattern()
{
    for(int i=0,j=0;i<m;i++)
    {
        while(str[i]!=sub[j] && j>0)
            j=pattern[j-1];
        if(str[i]==sub[j])
        {
            if(j==n-1)
            {
                rez[counter++]=i-n+1;
                j=pattern[j];
            }
            else
                j++;
        }
    }
}
int main()
{
    fin >>sub>>str;
    n=sub.length();//strlen(sub);
    m=str.length();//strlen(str);
    makePattern();
    searchPattern();
   // printf("%d\n",counter);
    fout <<counter<<endl;
    for(int i=0;i<counter && i<1000;i++)
    //    printf("%d ",rez[i]);
        fout <<rez[i]<<" ";
    return 0;
}