Mai intai trebuie sa te autentifici.
Cod sursa(job #1010996)
Utilizator | Data | 16 octombrie 2013 00:31:25 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.3 kb |
#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 32857
#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;
while (hash2 < 0) hash2+=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;
}