Pagini recente » Cod sursa (job #708981) | Cod sursa (job #2550533) | Cod sursa (job #2197978) | Cod sursa (job #2094013) | Cod sursa (job #2835048)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, z[2000005], zz, num;
string s1, s2;
vector <int> rez;
void p_preg()
{
for(int i=1, l=0, r=0; i<n; i++)
{
if(i<=r) z[i]=min(z[i-l], r-i+1);
while(i+z[i]<n && s1[i+z[i]]==s1[z[i]])
z[i]++;
if(i+z[i]-1>r) l=i, r=i+z[i]-1;
}
}
void ZZ()
{
if(n>m) return;
for(int i=0, l=0, r=0; i<m; i++)
{
if(i<=r) zz=min(z[i-l], r-i+1);
while(i+zz<m && zz<n && s2[i+zz]==s1[zz])
zz++;
if(zz==n)
{
num++;
if(num<=1000) rez.push_back(i);
}
if(i+zz-1>r) l=i, r=i+zz-1;
zz=0;
}
}
int main()
{
fin >> s1 >> s2;
n=s1.length(), m=s2.length();
p_preg();
ZZ();
fout << num << "\n";
for(int i=0; i<rez.size(); i++) fout << rez[i] << " ";
return 0;
}