Pagini recente » Cod sursa (job #331211) | Cod sursa (job #2524019) | Cod sursa (job #1922792) | Cod sursa (job #1900899) | Cod sursa (job #1996007)
#include <fstream>
using namespace std;
ifstream fi ("strmatch.in");
ofstream fo ("strmatch.out");
string word,sir;
int i,start,poz,k;
int T[2000004],sol[1006];
void precalc()
{
int pcuv=1,psuf=0;
while (pcuv<word.size())
{
if (word[pcuv]==word[psuf])
{
pcuv++;
psuf++;
T[pcuv]=psuf;
}
else if (psuf>0) psuf=T[psuf];
else {pcuv++;T[pcuv]=0;}
}
T[0]=0;
T[1]=1;
}
int main()
{
fi>>word>>sir;
precalc();
// fo<<' '<<word<<'\n';
// for (i=0;i<word.size();i++) fo<<T[i];
while (start<=sir.size()-word.size())
{
if (poz==word.size()) {k++;sol[k]=start;if (k==1000) break;}
if (word[poz]==sir[poz+start]) poz++;
else {start=start+T[poz]+(T[poz]==0);poz=0;}
}
fo<<k<<'\n';
for (i=1;i<=k;i++) fo<<sol[i]<<' ';
return 0;
}