Cod sursa(job #1674789)

Utilizator FeriCsiki Francisc Alexandru Feri Data 4 aprilie 2016 20:56:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

const int N=2000001;

char a[N+1],b[N+1];

int pref[N],n,m,c[N];

void calc()
{
    int k=0,i;
    for(i=2;i<=m;i++)
    {
        while(k>0 && a[k+1]!=a[i])
        {
            k=pref[k];
        }
        if(a[k+1]==a[i])
            k++;
        pref[i]=k;
    }
}

int main()
{
    int i,l=0;
    in.getline(a+1,N);
    in.getline(b+1,N);
    n=strlen(b+1);
    m=strlen(a+1);
    calc();
    int k=0;
    for(i=1;i<=n;i++)
    {
        while(k>0 && a[k+1]!=b[i])
            k=pref[k];
        if(a[k+1]==b[i])
            k++;
        if(k==m)
        {
            l++;
            c[l]=i-m+1;
        }
    }
    out<<l<<'\n';
    for(i=1;i<=l;i++)
    {
        out<<c[i]-1<<" ";
    }
    return 0;
}