Pagini recente » Cod sursa (job #3262077) | Cod sursa (job #2604186) | Cod sursa (job #466500) | Cod sursa (job #2979684) | Cod sursa (job #3215954)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define pb push_back
#define fr first
#define sc second
#define vt vector
#define ub upper_bound
#define lb lower_bound
using namespace std;
string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int NMAX = 4e6;
int kmp[NMAX + 1];
void KMP(string s){
kmp[1] = 0;
for(int i = 2; i < sz(s); i++){
int l = kmp[i - 1];
while(l > 0 && s[l + 1] != s[i]){
l = kmp[l];
}
if(s[l + 1] == s[i]){
kmp[i] = l + 1;
}
}
}
int main(){
string a, b;
fin >> a >> b;
string s = "$" + a + "$" + b;
KMP(s);
int ans = 0;
vt <int> pos;
for(int i = sz(a) + 2; i < sz(s); i++){
if(kmp[i] == sz(a)){
ans++;
if(sz(pos) <= 1000){
pos.pb(i - 2 * sz(a) - 1);
}
}
}
fout << ans << '\n';
for(int x : pos){
fout << x << ' ';
}
fout << '\n';
return 0;
}