Pagini recente » Cod sursa (job #373349) | Cod sursa (job #2394098) | Cod sursa (job #2012978) | Cod sursa (job #245596) | Cod sursa (job #1010979)
#include <stdio.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;
inline bool validChar(char c)
{
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A, sizeof(A), stdin);
fgets(B, sizeof(B), stdin);
n = m = 1;
while (validChar(A[n]))
n++;
while (validChar(B[m]))
m++;
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.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;
}