Pagini recente » Cod sursa (job #2254051) | Cod sursa (job #1645287) | Cod sursa (job #1448679) | Cod sursa (job #54545) | Cod sursa (job #2256339)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define sz(x) (int)((x).size())
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > vll;
typedef vector< pii > vpii;
typedef vector< pll > vpll;
typedef long double ld;
const ll MOD = 1e9 + 7;
ll lgput(ll a, ll b, ll mod) {
ll ret = 1;
while( b ){
if(b & 1) ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret;
}
int binarySearch(vector< int > &v, int value) {
int best = 0;
for(int step = 29; step >= 0; --step) {
if(best + (1<<step) < v.size() && v[best + (1<<step)] <= value) best += (1<<step);
}
return best;
}
inline ll inv(ll x, ll MOD) {
return lgput(x, MOD - 2, MOD);
}
const int MAXN = 1010;
int sol[MAXN];
int cnt = 0;
int pi[MAXN];
int main() {
// freopen("input", "r", stdin); freopen("output", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(12);
cout << fixed;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
f >> a >> b;
a = '#' + a;
b = '#' + b;
int n = sz(a);
int m = sz(b);
int q = 0;
for(int i = 2; i < n; ++i) {
while(q && a[q+1] != a[i]) q = pi[q];
if(a[q+1] == a[i]) ++q;
pi[i] = q;
}
q = 0;
for(int i = 1; i < m; ++i) {
while(q && a[q+1] != b[i]) q = pi[q];
if(a[q+1] == b[i]) ++q;
if(q == n - 1) {
q = pi[n-1];
++cnt;
if(cnt <= 1000) sol[cnt] = i - n + 1;
}
}
g << cnt << '\n';
for(int i = 1; i <= min(1000, cnt); ++i) g << sol[i] << ' ';
}