Pagini recente » Cod sursa (job #1773238) | Cod sursa (job #2095244) | Cod sursa (job #2190156) | Monitorul de evaluare | Cod sursa (job #774531)
Cod sursa(job #774531)
#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 <= min(1000, sol[0]); ++i)
printf("%d ", sol[i]);
return 0;
}