Pagini recente » Cod sursa (job #391786) | Cod sursa (job #2479272) | Cod sursa (job #676304) | Cod sursa (job #551960) | Cod sursa (job #2644657)
#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
*/
void solve() {
string a, b;
cin >> a >> b;
int n = a.size();
int m = b.size();
vector < int > dp(n, 0);
int i = 1, j = 0;
dp[0] = 0;
while(i < n) {
if(a[i] == a[j]) {
j++;
dp[i] = j;
i++;
} else {
if(j != 0) {
j = dp[j - 1];
} else {
dp[i] = 0;
i++;
}
}
}
int contor = 0;
vector < int > sol;
i = 0, j = 0;
while(i < m) {
if(a[j] == b[i]) {
i++;
j++;
}
if(j == n) {
++contor;
sol.push_back(i - j);
if(contor == 1000) {
cout << contor << endl;
for(auto it : sol) {
cout << it << " ";
}
return;
}
j = dp[j - 1];
} else if(i < m && a[j] != b[i]) {
if(j != 0) {
j = dp[j - 1];
} else {
i++;
}
}
}
cout << contor << 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();
}
}