Cod sursa(job #1675938)

Utilizator GinguIonutGinguIonut GinguIonut Data 5 aprilie 2016 17:25:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
#include <string.h>

#define nMax 2000001
#define pb push_back
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, nrSol;
int pi[nMax], Sol[1001];
char A[nMax], B[nMax];
void read()
{
    fin>>A+1>>B+1;

    n=strlen(A+1);
    m=strlen(B+1);
}
void kmp(char A[], char B[])
{
    int k=0;

    for(int 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;
    }
    k=0;

    for(int i=1;i<=m;i++)
    {
        while(k && A[k+1]!=B[i])
            k=pi[k];

        if(A[k+1]==B[i])
            k++;

        if(k==n)
        {
            nrSol++;
            if(nrSol<=1000)
                Sol[nrSol]=i-n;
            k=pi[k];
        }
    }
}
void solve()
{
    kmp(A, B);
}
void write()
{
    fout<<nrSol<<'\n';
    for(int i=1;i<=min(nrSol, 1000);i++)
        fout<<Sol[i]<<" ";
}
int main()
{
    read();
    solve();
    write();
    return 0;
}