Pagini recente » Cod sursa (job #691202) | Cod sursa (job #1745037) | Cod sursa (job #981961) | Cod sursa (job #1766982) | Cod sursa (job #2834998)
#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[2000005], num;
string s1, s2;
vector <int> rez;
void ZZ()
{
if(n>m) return;
for(int i=1, l=0, r=0; i<m; i++)
{
if(i<=r) zz[i]=min(z[i-l], r-i+1);
while((i+zz[i]<m && zz[i]<n) && s2[i+zz[i]]==s1[zz[i]])
zz[i]++;
if(zz[i]==n)
{
num++;
if(num<=1000) rez.push_back(i);
}
if(i+zz[i]-1>r) r=i+zz[i]-1;
}
}
int main()
{
fin >> s1 >> s2;
n=s1.length(), m=s2.length();
ZZ();
fout << num << "\n";
for(int i=0; i<rez.size(); i++) fout << rez[i] << " ";
return 0;
}