Pagini recente » Cod sursa (job #988410) | Cod sursa (job #1804875) | Cod sursa (job #1328050) | Cod sursa (job #1678297) | Cod sursa (job #2644669)
#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;
void init(string a, vector < int > &dp) {
int j = 0;
dp[0] = -1;
int i = 1;
while(i < a.size()) {
if(a[i] == a[j]) {
j++;
dp[i] = j;
i++;
} else {
if(j != 0) {
j = dp[j - 1];
} else {
dp[i] = 0;
i++;
}
}
}
}
void cauta(string a, string b) {
int m = a.size();
int n = b.size();
vector < int > dp(m, 0);
init(a, dp);
int i = 0;
int j = 0;
while(i < n) {
if(a[j] == b[i]) {
i++;
j++;
}
if(j == m) {
sol.push_back(i - j);
if(sol.size() > 1000) {
return;
}
j = dp[j - 1];
} else if(i < n && a[j] != b[i]) {
if(j != 0) {
j = dp[j - 1];
} else {
i++;
}
}
}
}
void solve() {
string a, b;
cin >> a >> b;
cauta(a, b);
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();
}
}