Pagini recente » Cod sursa (job #2828378) | Cod sursa (job #2821723) | Cod sursa (job #456392) | Cod sursa (job #1984888) | Cod sursa (job #1690668)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#define NMAX 2000000
using namespace std;
FILE * in, *out;
char s[NMAX],pattern[NMAX];
int n, np;
int power;
int base = 74;
int h(char * s, int start, int length);
int update(int x, int i, char * sir);
int code_pattern;
void read();
void solve();
int main()
{
in = fopen("strmatch.in", "r");
out = fopen("strmatch.out", "w");
read();
code_pattern = h(pattern,0,np);
//printf("%d", code_pattern);
power = pow((double)base,(double)np);
solve();
return 0;
}
void read()
{
fscanf(in,"%s",&pattern);
fscanf(in, "%s", &s);
n = strlen(s);
np = strlen(pattern);
//printf("%s\n%s", pattern, s);
}
int h(char * s, int start, int length)
{
int code = 0;
int p = 1;
for (int i = start + length - 1; i >= start; i--)
{
code += (s[i] - '0') * p;
p = p*base;
}
return code;
}
int update(int x, int i, char * sir)
{
int y;
int aux;
y = x*base - (sir[i - 1]- '0') * power + (sir[i + np - 1]-'0');
return y;
}
void solve()
{
queue<int> q;
int hsubsir = h(s, 0, np);
for (int i = 1; i <= n - np+1; i++)
{
if (hsubsir == code_pattern)
q.push(i-1);
hsubsir = update(hsubsir, i, s);
}
fprintf(out, "%d\n", q.size());
int dim = q.size();
for (int i = 0; i <dim ; i++)
{
fprintf(out, "%d ", q.front());
q.pop();
}
}