Pagini recente » Cod sursa (job #876633) | Cod sursa (job #1854584) | Cod sursa (job #783536) | Cod sursa (job #1610024) | Cod sursa (job #878145)
Cod sursa(job #878145)
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
void redirectInput(const char *in, const char *out)
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
}
int hash(char *s, int start, int l)
{
int hash = 0;
for(int i = start; i < l; ++i)
{
hash += s[i];
}
return hash;
}
int hash(char *s, int start, int l, int prevHash)
{
return prevHash - s[start - 1] + s[start + l];
}
void solve()
{
vector<int> matches;
char *a = (char*) calloc(2000000, sizeof(char));
char *b = (char*) calloc(2000000, sizeof(char));
scanf("%s %s", a, b);
int n = strlen(a);
int m = strlen(b);
if( m < n )
return;
int hs = hash(a, 0, n);
int h = hash(b, 0, n);
if( h == hs && strncmp(a, b, n) == 0)
{
matches.push_back(0);
}
for(int i = 1; i < m - n; ++i)
{
h = hash(b, i, n, h);
if(h == hs)
{
if( strncmp(a, b + i, n) == 0)
matches.push_back(i);
}
}
int n_to_print = (matches.size() > 1000) ? 1000 : matches.size();
printf("%lu\n", matches.size());
for(int i = 0; i < n_to_print; ++i)
printf("%d ", matches[i]);
}
int main(int argc, char *argv[])
{
if(argc != 2)
redirectInput("strmatch.in", "strmatch.out");
else
redirectInput(argv[1], "strmatch.out");
solve();
return 0;
}