Cod sursa(job #2074391)

Utilizator CristinaGTTirsi Cristina Gabriela CristinaGT Data 24 noiembrie 2017 15:54:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n,v[2000002],k,ap[1001];
char s[2000002],c[2000002];

void prefix()
{
    int i,j;
    s[0]=' ';
    n=strlen(s)-1;
    v[0]=v[1]=1;
    j=1;
    for(i=2;i<=n;i++)
    {
        if(s[i]==s[j])
            v[i]=++j;
        else
        {
            j=v[j-1];
            while(s[j]!=s[i] && j!=1)
                j=v[j-1];
            if(j==1 && s[i]!=s[j]) v[i]=1;
            else
            v[i]=++j;
        }
    }
}

void kmp()
{
    int i,j;
    c[0]=' ';
    int m=strlen(c)-1;
    j=1;
    for(i=1;i<=m;i++)
    {
        if(c[i]==s[j])
            {
                if(j==n)
                    {
                        if(k<1000)
                            ap[++k]=i-n;
                        else k++;
                        j=v[j];
                    }
                else
                j++;
            }
        else if(j!=1)
        {
            j=v[j-1];
            i--;
        }
    }
}

int main()
{
    fin>>(s+1);
    int i,j;
    prefix();
    fin>>(c+1);
    kmp();
    fout<<k<<'\n';
    for(i=1;i<=k && i<=1000;i++)
        fout<<ap[i]<<" ";
    fout<<'\n';
   /* for(i=1;i<=n;i++)
        fout<<v[i]<<" ";*/
    return 0;
}