Cod sursa(job #1769961)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 3 octombrie 2016 15:50:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 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 {
//            fprintf(fout, "a[crPref + 1]: %c, a[i]: %c\n", a[crPref + 1], a[i]);
            if(a[i] == a[crPref + 1]) {
                break;
            } else {           
              crPref = pref[crPref];
            }
        } while(crPref != 0);
        
        if(a[i] == a[crPref + 1]) {
            crPref += 1;
        }
        pref[i] = crPref;
//        fprintf(fout, "%c, pref[%d]: %d\n", a[i], 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 <= 1000 ; i++) {
        fprintf(fout, "%d ", matches[i] - 1 );
    }
    
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}