Pagini recente » Cod sursa (job #1071061) | Cod sursa (job #2678723) | Cod sursa (job #2773827) | Cod sursa (job #1568457) | Cod sursa (job #3159473)
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6 + 5;
typedef long long ll;
int k, lps[2*N];
char c1[N], c2[N], v[2*N];
vector<int> ans;
int main()
{
in >> c1;
in >> c2;
int n = strlen(c1), m = strlen(c2);
k = -1;
for(int i=0; i<n; i++)
v[++k] = c1[i];
v[++k] = '#';
for(int i=0; i<m; i++)
v[++k] = c2[i];
k++;
for(int i=1; i<k; i++) {
int j = lps[i-1];
while(j > 0 && v[i] != v[j])
j = lps[j-1];
if(v[i] == v[j])
j++;
lps[i] = j;
if(lps[i] == n) {
ans.pb(i - n * 2);
}
}
out << ans.size() << '\n';
if(ans.size() <= 1000)
for(int i=0; i<ans.size(); i++)
out << ans[i] << ' ';
else
for(int i=0; i<1000; i++)
out << ans[i] << ' ';
return 0;
}