Pagini recente » Cod sursa (job #1265144) | Cod sursa (job #351787) | Cod sursa (job #1828856) | Cod sursa (job #1936506) | Cod sursa (job #1010986)
#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 65535
#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)
{
long long hash = 0;
FOR (i,0,n-1)
hash = (hash*BASE + A[i]) % MOD;
long long hash2 = 0;
FOR (i,0,n-1)
hash2 = (hash2*BASE + B[i]) % MOD;
long long 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());
FOR (i,0,matches.size()-1)
{
printf("%d ",matches[i]);
if (i == 999)
break;
}
return 0;
}