Cod sursa(job #1716516)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 12 iunie 2016 23:17:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#define lim 2000005
#define stop 1000
int n,m;
int pi[lim],rasp[stop+5];
char v[lim],u[lim];
bool verif(char ch){
    if(ch>='A'&&ch<='Z')
        return true;
    if(ch>='a'&&ch<='z')
        return true;
    if(ch>='0'&&ch<='9')
        return true;
    return false;
}
void prefix(){
    int i,poz=0;
    for(i=2;i<=n;i++){
        while(poz!=0&&v[poz+1]!=v[i])
            poz=pi[poz];
        if(v[poz+1]==v[i])
            poz++;
        pi[i]=poz;
    }
}
int main(){
    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    int i,poz=0,k=0;
    i=1;
    fscanf(fin,"%c",&v[i]);
    while(verif(v[i])==true){
        i++;
        fscanf(fin,"%c",&v[i]);
    }
    n=i-1;
    i=1;
    fscanf(fin,"%c",&u[i]);
    while(verif(u[i])==true){
        i++;
        fscanf(fin,"%c",&u[i]);
    }
    m=i-1;
    prefix();
    for(i=1;i<=m;i++){
        while(poz!=0&&v[poz+1]!=u[i])
            poz=pi[poz];
        if(v[poz+1]==u[i])
            poz++;
        if(poz==n&&k<stop){
            poz=pi[n];
            k++;
            rasp[k]=i-n;
        }
    }
    fprintf(fout,"%d\n",k);
    if(k>stop)
        k=stop;
    for(i=1;i<=k;i++)
        fprintf(fout,"%d ",rasp[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}