Cod sursa(job #1968523)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 17 aprilie 2017 18:53:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <queue>

using namespace std;

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

#define nmax 2000010
char a[nmax],b[nmax];
int n,m,i,ans[1010],nr,pi[nmax];

void prefix()
{
    pi[1]=0;
    int k=0;
    for (i=2; i<=n; i++)
    {
        while (k&&a[k+1]!=a[i])
            k=pi[k];
        if (a[k+1]==a[i])
            k++;
        pi[i]=k;
    }
}

void kmp()
{
    int q=0;
    for (i=1; i<=m; i++)
    {
        while (q&&a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            q++;
        if (q==n)
        {
            q=pi[n];
            nr++;
            if (nr<=1000)
                ans[nr]=i-n;
        }
    }
}

int main()
{
    fin >> a >> b;
    n=strlen(a);
    m=strlen(b);
    for (i=n; i; i--)
        a[i]=a[i-1];
    for (i=m; i; i--)
        b[i]=b[i-1];
    prefix();
    kmp();
    fout << nr << '\n';
    for (i=1; i<=min(1000,nr); i++)
        fout << ans[i] << ' ';
    fout << '\n';
//    for (i=1; i<=n; i++)
//        fout << pi[i] << ' ';
}