Pagini recente » Cod sursa (job #2280315) | Cod sursa (job #1998700) | Cod sursa (job #884583) | Cod sursa (job #1256015) | Cod sursa (job #2793359)
#include <iostream>
#include <stdio.h>
using namespace std;
#define BAZA 62
#define MOD1 1000007
#define MOD2 666013
#define MAXLENGHT 2000000
#define MAXOUT 1000
char pat[MAXLENGHT], v[MAXLENGHT];
int out[MAXOUT];
int hpat[2], hss[2], put[2];
int verif(int n, int st, int dr){
int i, f = 1;
i = 0;
while(( f ) && (i < n)){
if(pat[i] != v[i + st]){
f = 0;
}
i++;
}
return f;
}
int main()
{
FILE *fin, *fout;
char ch;
int i, n, ind, cod, codaux, additional;
ch = 0;
i = 0;
hpat[0] = 0;
fin = fopen("strmatch.in", "r");
while((ch = fgetc(fin)) != '\n'){
pat[i] = ch;
if(('A' <= ch) && (ch <= 'Z')){
cod = ch - 'A';
}else if(('a' <= ch) && (ch <= 'z')){
cod = ch - 'a' + 26;
}else{
cod = ch - '0' + 52;
}
hpat[0] = (BAZA * hpat[0] + cod) % MOD1;
hpat[1] = (BAZA * hpat[1] + cod) % MOD2;
i++;
}
n = i;
i = 0;
ch = 0;
ind = 0;
put[0] = put[1] = 1;
additional = 0;
while(((ch = fgetc(fin)) != '\n') && (ch != EOF)){
v[i] = ch;
if(('A' <= ch) && (ch <= 'Z')){
cod = ch - 'A';
}else if(('a' <= ch) && (ch <= 'z')){
cod = ch - 'a' + 26;
}else{
cod = ch - '0' + 52;
}
if(i < n){
hss[0] = (BAZA * hss[0] + cod) % MOD1;
hss[1] = (BAZA * hss[1] + cod) % MOD2;
if(i == (n - 1)){
if((hss[0] == hpat[0]) && (hss[1] == hpat[1])){
if(verif(n, 0, i + 1)){
out[ind] = i - n + 1;
ind++;
}
}
}else{
put[0] = (put[0] * BAZA) % MOD1;
put[1] = (put[1] * BAZA) % MOD2;
}
}else{
if(('A' <= v[i - n]) && (v[i - n] <= 'Z')){
codaux = v[i - n] - 'A';
}else if(('a' <= v[i - n]) && (v[i - n] <= 'z')){
codaux = v[i - n] - 'a' + 26;
}else{
codaux = v[i - n] - '0' + 52;
}
hss[0] = hss[0] - (codaux * put[0]) % MOD1;
hss[1] = hss[1] - (codaux * put[1]) % MOD2;
if(hss[0] < 0){
hss[0] += MOD1;
}
if(hss[1] < 0){
hss[1] += MOD2;
}
hss[0] = (hss[0] * BAZA + cod) % MOD1;
hss[1] = (hss[1] * BAZA + cod) % MOD2;
if((hss[0] == hpat[0]) && (hss[1] == hpat[1])){
if(verif(n, i - n + 1, i + 1)){
if(ind < MAXOUT){
out[ind] = i - n + 1;
ind++;
}else{
additional++;
}
}
}
}
i++;
}
fclose(fin);
fout = fopen("strmatch.out", "w");
fprintf(fout, "%d\n", ind + additional);
for(i = 0; i < ind; i++){
fprintf(fout, "%d ", out[i]);
}
fclose(fout);
return 0;
}