Pagini recente » Cod sursa (job #367933) | Cod sursa (job #2044641) | Cod sursa (job #1259528) | Cod sursa (job #696507) | Cod sursa (job #1213144)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
string s1,s2;
int phi[2000001],poz[1001];
void computePhi(string s,long size)
{
int i,k;
k=0;
phi[1]=0;
for(i=2;i<=size;++i)
{
while(k>0 && 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");
int aparitii=0;
int i,k,n,m;
f>>s1>>s2;
s1.insert(0," ");
s2.insert(0," ");
n=s1.size();
m=s2.size();
computePhi(s1,n);
k=0;
for(i=1;i<=m;++i)
{
while(k>0 && s1[k+1]!=s2[i])
k=phi[k];
if(s1[k+1]==s2[i]) ++k;
if(k==n-1)
{
if(aparitii<1000)
{
poz[++aparitii]=i-n+1;
}
}
}
g<<aparitii<<"\n";
for(i=1;i<=aparitii;++i) g<<poz[i]<<" ";
f.close();
g.close();
return 0;
}