Pagini recente » Cod sursa (job #1740528) | Cod sursa (job #2863579) | Cod sursa (job #382110) | Cod sursa (job #847181) | Cod sursa (job #1253774)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m;
int pi[2000001];
string a,b;
void makepie();
int main()
{
f>>a>>b;
n = a.size();
m = b.size();
a.insert(a.begin(),1,' ');
b.insert(b.begin(),1,' ');
vector<int> sl;
int nr=0;
makepie();
for(int i = 1, q = 0; i <= m; i++){
while(q && a[q+1] != b[i])
q = pi[q];
if(a[q+1] == b[i])
q++;
if(q == n){
nr++;
if(sl.size()<1000)
sl.push_back(i - n);
}
}
g<<nr<<'\n';
for(size_t i = 0;i < sl.size(); i++)
g<<sl[i]<<" ";
return 0;
}
void makepie()
{
int q = 0;
for(int i = 2; i<=n ; i++){
while(q && a[q+1] != a[i])
q = pi[q];
if(a[q+1] == a[i])
q++;
pi[i] = q;
}
}