Pagini recente » Cod sursa (job #1129511) | Cod sursa (job #2702748) | Cod sursa (job #1958104) | Cod sursa (job #1181068) | Cod sursa (job #2465418)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int z[2000004];
int r,l;
string s1, s2;
void findin(string c, string st)
{
string s=c+"*"+st+"$";
int t;
z[1]=0;
int n=s.size();
int k=2;
for(k=2;k<s.size();++k)
{
if(k>r)
{
l=r=k;
while(r<n && s[r-l] == s[r])
r++;
z[k]=r-l;
r=r-1;
} else {
t=k-l;
if(z[t] < r-k+1)
z[k]=z[t];
else {
l=k;
while(s[r] == s[r-l] && r<n)
r++;
z[k]=r-l;
r=r-1;
}
}
}
int m=c.size();
int mys=0;
for(int i=m+1;i<=st.size()+m+1;++i)
{
if(z[i]==c.size())
mys++;
}
g<<mys<<"\n";
for(int i=m+1;i<=st.size()+m+1;++i)
{
if(z[i]==c.size())
g<<i-m-1<<" ";
}
}
int main()
{
f>>s1>>s2;
findin(s1,s2);
return 0;
}