Pagini recente » Cod sursa (job #492425) | Cod sursa (job #491091) | Cod sursa (job #1134725) | Cod sursa (job #2011676) | Cod sursa (job #774530)
Cod sursa(job #774530)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
const int maxn = 2000005;
using namespace std;
int n, m;
char a[maxn], b[maxn];
int perm[maxn], sol[maxn];
inline void swap(int &a, int &b) {
int aux = a; a = b; b = aux;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", a , b);
n = strlen(a); m = strlen(b);
//let's try more of a randomized matching
srand(time(NULL));
for(int i = 0; i < n; ++i)
perm[i] = i;
for(int i = 0; i < m - n; ++i) {
int j;
for(j = 0; j < n; ++j) {
int pos = rand() % (n - j + 1);
if(a[perm[pos]] != b[i + perm[pos]]) break;
swap(perm[pos], perm[n - j]);
}
if(j == n) {
sol[++sol[0]] = i;
}
}
printf("%d\n", sol[0]);
for(int i = 1; i <= sol[0]; ++i)
printf("%d ", sol[i]);
return 0;
}