Cod sursa(job #2305107)

Utilizator filicriFilip Crisan filicri Data 19 decembrie 2018 09:51:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <string>
#define lim 2000004
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pre[lim],na,nb,ap[lim];
string a,b;
void prefix (void)
{
    int j=0;
    for (int i=2;i<=na;i++)
    {
        while (j && a[j+1]!=a[i]) j=pre[j];
        if (a[j+1]==a[i]) j++;
        pre[i]=j;
    }
}
int main()
{
    f>>a>>b;
    na=a.length();
    nb=b.length();
    for (int i=na-1;i>=0;i--) a[i+1]=a[i];
    for (int i=nb-1;i>=0;i--) b[i+1]=b[i];
    prefix();
    int j=0;
    for (int i=1;i<=nb;i++)
    {
        while (j && a[j+1]!=b[i]) j=pre[j];
        if (a[j+1]==b[i]) j++;
        if (j==na)
        {
            j=pre[j];
            if (ap[0]<1000)
            {
                ap[0]++;
                ap[ap[0]]=i-na+1;
            }
        }
    }
    g<<ap[0]<<'\n';
    for (int i=1;i<=ap[0];i++) g<<ap[i]-1<<' ';
    f.close();
    g.close();
    return 0;
}