Cod sursa(job #2716530)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 5 martie 2021 12:07:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;
char a[2000000],b[2000000];
int save[1000000];

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    int n,m,pi[2000000],cnt=0;
    in>>(a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    pi[1]=0;
    int lung =0;
    for(int i=2;i<=n;i++)
    {
        while(lung>0 && a[i]!=a[lung+1])
        {
            lung=pi[lung];
        }
        if(a[i]==a[lung+1])
        {
            lung++;
        }
        pi[i]=lung;
    }
    lung=0;
    for(int i=1;i<=m;i++)
    {
        while(lung>0 && b[i]!=a[lung+1])
        {
            lung=pi[lung];
        }
        if(b[i]==a[lung+1])
        {
            lung++;
        }
        if(lung==n)
        {
           save[cnt++]=i-n;
        }
    }
    out<<cnt<<"\n";
    for(int i=0;i<cnt;i++)
    {
        out<<save[i]<<" ";
    }
    return 0;
}