Pagini recente » Cod sursa (job #1001809) | Cod sursa (job #1676891) | Cod sursa (job #2970431) | Cod sursa (job #199019) | Cod sursa (job #1213114)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
string s1,s2;
int phi[2000001],poz[2000001];
void computePhi(string s)
{
long i,k,n;
k=-1;
phi[0]=0;
n=s.size();;
for(i=1;i<n;++i)
{
while(k>-1 && s[k+1]!=s[i])
k=phi[k];
if(s[k+1]==s[i]) ++k;
phi[i]=k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long aparitii=0;
long i,k,n,m;
f>>s1>>s2;
n=s1.size();
m=s2.size();
computePhi(s1);
k=-1;
for(i=0;i<m;++i)
{
while(k>-1 && s1[k+1]!=s2[i])
k=phi[k];
if(s1[k+1]==s2[i]) ++k;
if(k==n-1)
poz[++aparitii]=i-n+1;
}
g<<aparitii<<"\n";
for(i=1;i<=aparitii;++i) g<<poz[i]<<" ";
f.close();
g.close();
return 0;
}