Pagini recente » Cod sursa (job #1439769) | Cod sursa (job #2476063) | Cod sursa (job #2973992) | Cod sursa (job #2455945) | Cod sursa (job #2458143)
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int z[4000010];
void zz(string a)
{
int l=0;
int r=0;
z[0]=a.length();
for(int k=1; k<a.length(); k++)
{
if(k>r)
{
r=k;
l=k;
while(a[r]==a[r-l])
{
r++;
}
z[k]=r-l;
r--;
}
else
{
if(z[k-l]<r-k+1)
{
z[k]=z[k-l];
}
else
{
l=k;
while(a[r]==a[r-l])
{
r++;
}
z[k]=r-l;
r--;
}
}
}
}
void srch(string text,string pattern)
{
string res=pattern+text;
vector<int>results;
zz(res);
for(int i=1; i<res.length(); i++)
{
if(i>=pattern.length() && z[i]>=pattern.length())
{
results.push_back(i-pattern.length());
}
}
int index=results.size();
out<<index<<endl;
index=min(index,1000);
for(int i=0; i<index; i++)
out<<results[i]<<" ";
}
int main()
{
string a,b;
in>>a>>b;
srch(b,a);
return 0;
}