Cod sursa(job #1769949)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 3 octombrie 2016 15:06:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: octavian
 *
 * Created on 03 October 2016, 11:54
 */

#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX_STR_LEN = 2000005;
char a[MAX_STR_LEN];
char b[MAX_STR_LEN];
int pref[MAX_STR_LEN], matches[MAX_STR_LEN];

int lenA, lenB;

/*
 * 
 */
int main(int argc, char** argv) {

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

    fscanf(fin, "%s", a + 1);
    fscanf(fin, "%s", b + 1);
    
    lenA = strlen(a + 1);
    lenB = strlen(b + 1);
    
//    fprintf(fout, "%s\n", (b + 1));
    
//    fprintf(fout, "lenA: %d\n", lenA);
//    fprintf(fout, "lenB: %d\n", lenB);
    
    int crPref = 0;
    for(int i = 2 ; i <= lenA ; i++) {
        do {
            if(a[i] == a[crPref + 1]) {
                crPref += 1;
            } else {           
              crPref = pref[crPref];
            }
        } while(a[i] != a[crPref] && crPref != 0);
        pref[i] = crPref;
//        fprintf(fout, "pref[%d]: %d\n", i, pref[i]);
    }
    
    int crMatch = 0;
    for(int i = 1 ; i <= lenB ; i++) {
        while(a[crMatch+1] != b[i] && crMatch != 0) {
            crMatch = pref[crMatch];
        }
        if(a[crMatch + 1] == b[i]) {
            crMatch += 1;
            if(crMatch == lenA) {
                matches[++matches[0]] = i - crMatch + 1;
            }
        }
//        fprintf(fout, "for %d: crMatch is %d\n", i, crMatch);
    }
    
    fprintf(fout, "%d\n", matches[0]);
    for(int i = 1 ; i <= matches[0] ; i++) {
        fprintf(fout, "%d ", matches[i] - 1 );
    }
    
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}