Pagini recente » Cod sursa (job #350403) | Cod sursa (job #79210) | Cod sursa (job #1374660) | Cod sursa (job #1767406) | Cod sursa (job #1213109)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
char s1[2000001],s2[2000001];
int phi[2000001],poz[2000001];
void computePhi(char *s)
{
long i,k,n;
k=-1;
phi[0]=0;
n=strlen(s);
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;
f>>s2;
computePhi(s1);
k=-1;
n=strlen(s1);
m=strlen(s2);
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;
}