Pagini recente » Cod sursa (job #1701522) | Cod sursa (job #1735294) | Cod sursa (job #2131755) | Cod sursa (job #1314996) | Cod sursa (job #1196661)
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <string>
#include <iterator>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
#define DMAX 2000001
#define MOD 140611
#define MOD2 1000000007
#define LIM 100000
#define MAX(a,b) a>b ? a : b
int D = 53, M, N, nrS, i, j;
char Px[DMAX], Tx[DMAX];
vector<int> S;
void match(int s){
nrS++;
if (nrS <= 1000) S.push_back(s);
}
inline int index(char c){
return c >= 'A' && c <= 'Z' ? c - 'A' + 1 : 26 + c - 'a' + 1;
}
void RK (string P, string T){
int hashP(0), hashT(0), hashD(1);
for (i = 0; i < M; i++){
hashP *= D, hashP += index(P[i]), hashP %= MOD;
hashT *= D, hashT += index(T[i]), hashT %= MOD;
if (i) hashD *= D, hashD %= MOD;
}
for (i = 0; i <= N - M; i++){
if (hashT == hashP) match(i);
hashT = ((hashT + D*MOD - index(T[i]) * hashD)\
% MOD*D + index(T[i + M])) % MOD;
}
}
void BM (string P, string T){
int skip;
vector<int> Right(D, -1);
for (i = 0; i < M; i++) Right[index(P[i])] = i;
for (i = 0; i <= N - M; i += skip){
skip = 0;
for (j = M - 1; j >= 0; j--){
if (P[j] != T[i+j]){
skip = j - Right[index(T[i + j])];
skip = MAX(1, skip);
break;
}
}
if (skip == 0) match(i), skip = 1;
}
}
void KMP(string P, string T){
int maxps(0), k;
vector<int> Pattern(M + 1, 0);
Pattern[0] = -1;
for (i = 1; i<=M; i++){
k = Pattern[i - 1];
while (k != -1 && P[i - 1] != P[k])
k = Pattern[k];
Pattern[i] = k + 1;
}
for (i = j = 0; i < N; i++){
while (j >= 0 && P[j] != T[i]) j = Pattern[j];
if (++j == M) match(i - M + 1), j = Pattern[j];
}
}
void write(){
printf("%d\n", nrS);
for (i = 0; i < 1000 && i < nrS; i++){
printf("%d ", S[i]);
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", Px, Tx);
string P(Px), T(Tx);
M = P.size(); N = T.size();
//RK(P, T);
//KMP(P, T);
//BM(P, T);
if (M > N) printf("0\n");
//else if (P.size() <= 3 ) RK (P, T);
else if (P.size() <= LIM) KMP(P, T);
else BM (P, T);
write();
return 0;
}