Cod sursa(job #1944632)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 29 martie 2017 10:36:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int nmax=2000023;
char a[nmax],b[nmax];
int prefix[nmax];
vector<int>sol;
int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s%s",a+1,b+1);
    int n=strlen(a+1),m=strlen(b+1);
    int q=0;
    for(int i=2;i<=n;i++)
    {
        while(a[q+1]!=a[i]&&q!=0) q=prefix[q];
        if(a[q+1]==a[i]) ++q;
        prefix[i]=q;
    }
    q=0;
    int mar=0;
    for(int i=1;i<=m;i++)
    {
        while(a[q+1]!=b[i]&&q) q=prefix[q];
        if(a[q+1]==b[i]) ++q;
        if(q==n)
        {
            sol.push_back(i-q);
            ++mar;
            if(mar==1000) break;
            q=prefix[q];
        }
    }
    printf("%d\n",mar);
    for(int i=0;i<mar;i++) printf("%d ",sol[i]);
}