Pagini recente » Cod sursa (job #365519) | Cod sursa (job #1026650) | Cod sursa (job #2085541) | Cod sursa (job #1343221) | Cod sursa (job #2793265)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
#define MOD 1000007
#define MAXLENGHT 2000000
#define MAXOUT 1000
vector <int>h[MOD];
int pat[MAXLENGHT], v[MAXLENGHT], out[MAXOUT];///de pus pe char
int logput(int a, int p){
if(p == 1){
return a;
}else{
if((p % 2) == 0){
return logput(((long long)a * a) % MOD, p / 2);
}else{
return ((long long)a * logput(((long long)a * a) % MOD, p / 2)) % MOD;
}
}
}
int verif(int n, int st, int dr){
int i, f = 1;
for(i = 0; i < n; i++){
if(pat[i] != v[i + st]){
f = 0;
}
}
return f;
}
int main()
{
FILE *fin, *fout;
char ch;
int i, n, hpat, hss, ind;
ch = 0;
i = 0;
hpat = 0;
fin = fopen("strmatch.in", "r");
while((ch = fgetc(fin)) != '\n'){
pat[i] = ch;
hpat = (26 * hpat + ch - 'A' + 1) % MOD;
i++;
}
n = i;
i = 0;
ch = 0;
hss = 0;
ind = 0;
while((ch = fgetc(fin)) != '\n'){
v[i] = ch;
if(ind < MAXOUT){
if(i < n){
hss = (26 * hss + ch - 'A' + 1) % MOD;
if(i == (n - 1)){
if(hss == hpat){
if(verif(n, 0, i + 1)){
out[ind] = i - n + 1;
ind++;
}
}
}
}else{
hss = hss - ((v[i - n] - 'A' + 1) * logput(26, n - 1)) % MOD;
if(hss < 0){
hss += MOD;
}
hss = (hss * 26 + ch - 'A' + 1) % MOD;
if(hss == hpat){
if(verif(n, i - n + 1, i + 1)){
out[ind] = i - n + 1;
ind++;
}
}
}
}
i++;
}
fclose(fin);
fout = fopen("strmatch.out", "w");
fprintf(fout, "%d\n", ind);
for(i = 0; i < ind; i++){
fprintf(fout, "%d ", out[i]);
}
fclose(fout);
return 0;
}