Cod sursa(job #2322359)

Utilizator vladboss2323Ciorica Vlad vladboss2323 Data 17 ianuarie 2019 18:29:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

char A[2000005],B[2000005];
int pi[2000005];
int main()
{
    int lc=0,poz[1005],nr=0,i,n,m;
    //in.getline(A,2000005);
    //in.getline(B,2000005);
    in>>A;//in >> (A + 1);
    in>>B;
    pi[0]=lc;
    for(i=strlen(A)+1; i>=1; i--)
        A[i]=A[i-1];
    for(i=strlen(B)+1; i>=1; i--)
        B[i]=B[i-1];
    n=strlen(A);
    m=strlen(B);
    for(i=2; i<n; i++)
    {
        while(lc>0 && A[i]!=A[lc+1])
        {
            lc=pi[lc];
        }
        if(A[i]==A[lc+1])
            lc++;
        pi[i]=lc;
    }
    lc=0;
    for(i=1; i<m; i++)
    {
        while(lc>0 && B[i]!=A[lc+1])
        {
            lc=pi[lc];
        }
        if(B[i]==A[lc+1])
            lc++;
        if(lc==strlen(A)-1)
        {
            nr++;
            if(nr<=1000)
                poz[nr]=i-n+1;
        }
    }
    out<<nr<<'\n';
    for(i=1; i<=nr; i++)
        out<<poz[i]<<" ";
    return 0;
}