Pagini recente » Cod sursa (job #2715567) | Cod sursa (job #1668118) | Cod sursa (job #1052012) | Cod sursa (job #1116047) | Cod sursa (job #1769961)
/*
* 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;
}