Pagini recente » Cod sursa (job #834740) | Cod sursa (job #1799006) | Cod sursa (job #442953) | Cod sursa (job #631856) | Cod sursa (job #1769949)
/*
* 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;
}