Pagini recente » Cod sursa (job #2725250) | Cod sursa (job #313521) | Cod sursa (job #2908644) | Cod sursa (job #2361088) | Cod sursa (job #2644780)
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define ll long long
#define endl "\n"
const int Nmax = 1500;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
/*
ifstream fin("test.in");
#define cin fin
*/
vector < int > sol;
string a, b;
int n, m;
void init(vector < int > & dp ) {
dp[1] = 0;
int j = 0;
for(int i = 2; i <= m; i++) {
while(j && a[j + 1] != a[i]) {
j = dp[j];
}
if(a[j + 1] == a[i]) {
j++;
}
dp[i] = j;
}
}
void cautare() {
vector < int > dp(m + 10, 0);
init(dp);
int j = 0;
for(int i = 1; i <= n; i++) {
while(j && a[j + 1] != b[i]) {
j = dp[j];
}
if(a[j + 1] == b[i]) {
j++;
}
if(j == m) {
sol.push_back(i - m);
if(sol.size() >= 1000) {
return;
}
}
}
}
void solve() {
cin >> a >> b;
n = b.size();
m = a.size();
a = "." + a;
b = "." + b;
cautare();
cout << sol.size() << endl;
for(auto it : sol) {
cout << it << " ";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin .tie(0);
cout.tie(0);
int testCases = 1;
//cin >> testCases;
while(testCases--) {
solve();
}
}