Cod sursa(job #1834990)

Utilizator zvonTutuldunsa Voronokda zvon Data 26 decembrie 2016 00:11:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<iostream>
#include<string>
#include<cstdlib>
#include<fstream>
#define NMAX 2000003
using namespace std;

char cuvant[NMAX];
char text[NMAX];
int values[1001];

int *getPrefixes(char w[], int n) {
     int *prefix = (int *) calloc (n, sizeof(int));
     int i = 1;
     int j = 0;
     while (i < n) {
          if (w[i] == w[j]) {
             prefix[i] = j + 1;
             i++;
             j++;
          } else if (j == 0) {
            i++;      
          } else {
            j = prefix[j - 1];
          }
     }
     return prefix;
}

int getIndexes(char w[], char s[], int n, int k, int prefix[]) {
     int m = 0;
     int i = 0;
     int count = 0;
     while (m < k - n + 1) {
           
           if (i == n) {
              //printf("%d ", m);
              //cout << s.substr(m, i) << '\n';
              values[count++] = m;
              m = m + i - prefix[i - 1];
              i = prefix[i - 1];
           }
           if (s[m + i] == w[i]) {
              i++;        
           } else if (i == 0 ){
              m = m + 1;
           } else {
              m = m + i - prefix[i];
              i = prefix[i - 1];       
           }
     }
     return count;
}

int main() {
    int n;
    int k;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    fgets(cuvant, NMAX, stdin);
    fgets(text, NMAX, stdin);
    n = strlen(cuvant) - 1;
    k = strlen(text) - 1;
   
    int* prefix = getPrefixes(cuvant, n);

    /*
    for (int i = 0; i < n; i++) {
        cout << prefix[i] << ' ';    
    }
    cout << '\n'; */
    
    int count = getIndexes(cuvant, text, n, k, prefix);
    cout << count << '\n';
    if (count > 1000)
       count = 1000;
    for (int i = 0; i < count; i++) {
        cout << values[i] << ' ';
    }
    
    return 0;
}