Pagini recente » Cod sursa (job #2941898) | Cod sursa (job #2240853) | Cod sursa (job #2232136) | Cod sursa (job #2550340) | Cod sursa (job #2682098)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define P 256
string A, B;
int sol[1010];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
fin >> A >> B;
int M = A.size();
int N = B.size();
int h = 1;
for (int i = 0; i < M - 1; i++) {
h = (h * P) % MOD;
}
int hashA = 0;
int hashB = 0;
for (int i = 0; i < M; i++) {
hashA = (hashA * P + A[i]) % MOD;
hashB = (hashB * P + B[i]) % MOD;
}
int count = 0;
for (int i = 0; i <= N - M; i++) {
if (hashA == hashB) {
int j;
for (j = 0; j < M; j++) {
if (B[i + j] != A[j])
break;
}
if (j == M && count < 1000) {
sol[count++] = i;
}
}
if (i < N - M) {
hashB = (P * (hashB - B[i] * h) + B[i + M]) % MOD;
if (hashB < 0)
hashB += MOD;
}
}
fout << count << "\n";
for (int i = 0; i < count; i++) {
fout << sol[i] << " ";
}
fout << "\n";
return 0;
}