Cod sursa(job #2372066)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 6 martie 2019 21:12:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
#define LMAX 2000005
char s[LMAX],t[LMAX];
int n,m,p[LMAX];
void make_prefix(){
    int q=0;
    p[1]=0;
    for(int i=2;i<=n;++i){
        while(q>0&&s[q+1]!=s[i])
            q=p[q];
        if(s[q+1]==s[i])
            ++q;
        p[i]=q;
    }
}
int poz[1005];
void match(){
    int q=0;
    for(int i=1;i<=m;++i){
        while(q>0&&s[q+1]!=t[i])
            q=p[q];
        if(s[q+1]==t[i])
            ++q;
        if(q==n){
            ++poz[0];
            if(poz[0]<=1000)
                poz[poz[0]]=i-n;
            q=p[q];
        }
    }
    printf("%d\n",poz[0]);
    for(int i=1;i<=min(1000,poz[0]);++i)
        printf("%d ",poz[i]);
}
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    make_prefix();
    scanf("%s",t+1);
    m=strlen(t+1);
    match();
    return 0;
}