Cod sursa(job #2302815)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 15 decembrie 2018 10:36:16
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
#define MaxLength 2000005
using namespace std;
char Text[MaxLength], Pattern[MaxLength];
int LT, LP, i, j, pi[MaxLength], List[1005], N; bool k;
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    fgets(Pattern, 101, stdin);
    fgets(Text, 101, stdin);
    LT=strlen(Text); LP=strlen(Pattern);
    if(Pattern[LP-1]=='\n') --LP;
    if(Text[LT-1]=='\n') --LT;
    for(i=1; i<LP; ++i) if(Pattern[pi[i-1]]==Pattern[i])pi[i]=pi[i-1]+1;
    for(i=0; i<LT; ++i){
        if(Text[i]==Pattern[0]){
            k=true;
            for(j=0; j<LP; ++j && ++i)
                if(Text[i]!=Pattern[j]) {i=i-pi[j-1]-1; k=false; break;}
            if(k==true){
                --i; ++N;
                if(N<=1000) List[N]=i-LP+1;
                i-=pi[LP-1];
            }
        }
    }
    printf("%d\n", N);
    for(i=1; i<=N && i<=1000; ++i)printf("%d ", List[i]);
    return 0;
}