Pagini recente » Cod sursa (job #1781451) | Autentificare | Cod sursa (job #1650045) | Cod sursa (job #2587364) | Cod sursa (job #1010997)
#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 100007
#define MOD2 100021
#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, kutya = 0;
FOR (i,0,n-1)
{
hash = (hash*BASE + A[i]) % MOD;
kutya = (kutya*BASE + A[i]) % MOD2;
}
int hash2 = 0,kutya2 = 0;
FOR (i,0,n-1)
{
hash2 = (hash2*BASE + B[i]) % MOD;
kutya2 = (kutya2*BASE + B[i]) % MOD2;
}
int exp = 1, exp2 = 1;
FOR (i,1,n-1)
{
exp = (exp*BASE) % MOD;
exp2 = (exp2*BASE) % MOD2;
}
if (hash == hash2 && kutya == kutya2)
matches.push_back(0);
FOR (i,n,m-1)
{
hash2 = (hash2 - exp*B[i-n]) % MOD;
hash2 = (hash2*BASE + B[i]) % MOD;
kutya2 = (kutya2 - exp2*B[i-n]) % MOD2;
kutya2 = (kutya2*BASE + B[i]) % MOD2;
while (hash2 < 0) hash2+=MOD;
while (kutya2 < 0) kutya2+=MOD2;
if (hash == hash2 && kutya == kutya2 && 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;
}