Cod sursa(job #1880012)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 15 februarie 2017 12:44:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

#define NMax 2000001

using namespace std;

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

int N,M;
char A[NMax],B[NMax];
int L[NMax],Sol[NMax];

void KMP()
{
    int k=0;
    for(int i=2;i<=N;i++)
    {
        while(A[i]!=A[k+1] && k>0)
            k=L[k];
        if(A[i]==A[k+1])
            k++;
        L[i]=k;
    }
    k=0;
    for(int i=1;i<=M;i++)
    {
        while(B[i]!=A[k+1] && k>0)
            k=L[k];
        if(B[i]==A[k+1])
            k++;
        if(k==N)
        {
            if(Sol[0]<1000)
                Sol[++Sol[0]]=i-k;
            else
                Sol[0]++;
            k=L[k];
        }
    }
}

int main()
{
    fin>>(A+1)>>(B+1);
    N=strlen(A+1);
    M=strlen(B+1);

    KMP();

    fout<<Sol[0]<<"\n";
    for(int i=1;i<=min(1000,Sol[0]);i++)
        fout<<Sol[i]<<" ";

    return 0;
}