Mai intai trebuie sa te autentifici.

Cod sursa(job #1572631)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 19 ianuarie 2016 00:00:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <string.h>

using namespace std;

FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");

char s[2000005], s2[2000005];
int pref[2000005], v[1001];

int main(){
    int i, j, l, L, q = 0, p = 0;
    char c;
    fscanf(fin, "%s", s);
    fscanf(fin, "%c", &c);
    fscanf(fin, "%s", s2);
    l = strlen(s);
    L = strlen(s2);
    for(i = l; i > 0; i--)
        s[i] = s[i - 1];
    for(i = L; i > 0; i--)
        s2[i] = s2[i - 1];
    s[0] = ' ';
    s2[0] = ' ';

    // GENERAREA PREFIXELOR
    i = 0;
    for(j = 2; j <= l; j++){
        while(i > 0 && s[i + 1] != s[j])
            i = pref[i];
        if(s[i + 1] == s[j])
            i++;
        pref[j] = i;
    }

    //KMP

    for(i = 1; i <= L ; i++){
        while(q != 0 && s[q + 1] != s2[i])
            q = pref[q];
        if(s[q + 1] == s2[i])
            q++;
        if(q == l){
            q = pref[l];
            p++;
            v[p] = i - l;
        }
    }

    // AFISARE

    fprintf(fout, "%d\n", p);
    if(p > 1000)
        p = 1000;
    for(i = 1; i <= p; i++)
        fprintf(fout, "%d ", v[i]);
    fprintf(fout, "\n");

    return 0;
}