Pagini recente » Cod sursa (job #165625) | Cod sursa (job #2793370) | Cod sursa (job #2357885) | Cod sursa (job #1900867) | Cod sursa (job #3141561)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6+2;
string a,b;
int n,m,p[NMAX];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
getline(fin, a);
getline(fin, b);
n = a.size();
m = b.size();
a = "$"+a;
b = "#"+b;
p[1] = 0;
int l = 0;
for(int i = 2; i <= n; i++){
while(l != 0 && b[i] != a[l+1]){
l = p[l];
}
if(b[i] == a[l+1]){
l++;
}
p[i] = l;
}
l = 0;
vector<int> ans;
for(int i = 1; i <= m; i++){
while(l != 0 && b[i] != a[l+1]){
l = p[l];
}
if(b[i] == a[l+1]){
l++;
}
if(l == n){
ans.push_back(i-n);
}
}
fout << min((int)ans.size(), 1000) << "\n";
for(int i = 0; i < ans.size() && i < 1000; i++){
fout << ans[i] << " ";
}
return 0;
}