Cod sursa(job #2339811)

Utilizator RedXtreme45Catalin RedXtreme45 Data 9 februarie 2019 12:51:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>

using namespace std;

  ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
char S[2000001];
char p[2000001];
int v[2000001],n,m,lps[2000001];

int kmp(int u)
{
    int i=0,j=0;
    while(i<n)
    {
        if (S[i]==p[j])
        {
            i++;
            j++;
            if (j==m)
            {
                u++;
                v[u]=i-m;
                j=lps[j-1];
            }
        }
        else
        {
            if (j==0)
                i++;
            else
                j=lps[j-1];
        }
    }
    return u;
}
int main()
{

    fin>>p;
    fin>>S;
    n=strlen(S);
    m=strlen(p);
    if (m>n)
        fout<<0;
    else
    {
        int i=1;
        int len=0;
        while (i<m)
        {
            if (p[i]==p[len])
            {
                len++;
                lps[i]=len;
                i++;
            }
            else
            {
                if (len==0)
                {
                    i++;

                }
                else
                    len=lps[len-1];
            }
        }
        int x=kmp(0);
        fout<<x<<"\n";
        for (int i=1; i<=x; i++)
        {
            fout<<v[i]<<" ";
        }
    }
    return 0;
}