Pagini recente » Cod sursa (job #1795943) | Cod sursa (job #2024539) | Monitorul de evaluare | Cod sursa (job #105983) | Cod sursa (job #1010993)
#include <stdio.h>
#include <string.h>
#include <vector>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define MAXN 2000001
#define MOD 65537
#define BASE 256
using namespace std;
char A[MAXN],B[MAXN];
int n,m;
vector<int> matches;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s", A, B);
n = strlen(A);
m = strlen(B);
if (m >= n)
{
int hash = 0;
FOR (i,0,n-1)
hash = (hash*BASE + A[i]) % MOD;
int hash2 = 0;
FOR (i,0,n-1)
hash2 = (hash2*BASE + B[i]) % MOD;
int exp = 1;
FOR (i,1,n-1)
exp = (exp*BASE) % MOD;
if (hash == hash2)
matches.push_back(0);
FOR (i,n,m-1)
{
hash2 = (hash2 - exp*B[i-n]) % MOD;
hash2 = (hash2*BASE + B[i]) % MOD;
if (hash == hash2 && matches.size() < 1000)
matches.push_back(i-n+1);
}
}
printf("%d\n",matches.size());
vector<int>::iterator it;
for (it = matches.begin(); it != matches.end(); ++it)
{
printf("%d ",*it);
}
return 0;
}