Pagini recente » Cod sursa (job #3001337) | Cod sursa (job #2136033) | Cod sursa (job #2235388) | Cod sursa (job #1590444) | Cod sursa (job #3286586)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define fr first
#define sc second
using namespace std;
string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
////////////////////////////////////////////////////////////
const int NMAX = 4e6;
int l[NMAX + 1]; // ?
void kmp(string s){
l[1] = 0;
for(int i = 2; i < sz(s); i++){
int x = l[i - 1];
while(x > 0 && s[i] != s[x + 1]){
x = l[x];
}
if(s[i] == s[x + 1]){
l[i] = x + 1;
}
}
}
void solve(){
string a, b;
fin >> a >> b;
int n = sz(a);
int m = sz(b);
string s = "$" + a + "$" + b;
kmp(s);
int ans = 0;
vt <int> pos;
for(int i = n + 2; i <= n + m + 1; i++){
if(l[i] == n){
ans += 1;
if(sz(pos) < 1000){
pos.pb(i - 2 * n - 1);
}
}
}
fout << ans << '\n';
for(int x : pos){
fout << x << ' ';
}
fout << '\n';
}
int main(){
int T;
//fin >> T;
T = 1;
while(T--){
solve();
}
return 0;
}