Pagini recente » Cod sursa (job #1858907) | Cod sursa (job #3249295) | Cod sursa (job #808586) | Cod sursa (job #2865474) | Cod sursa (job #1996017)
#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;
T[0]=-1;
while (pcuv<word.size())
{
if (word[pcuv]==word[psuf])
{
T[pcuv]=T[psuf];
pcuv++;
psuf++;
}
else
{
T[pcuv]=psuf;
while (psuf>0 and word[pcuv]!=word[psuf]) psuf=T[psuf];
pcuv++;psuf++;
}
}
}
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;start++;poz=0;}
if (word[poz]==sir[poz+start]) poz++;
else if (poz>0) {start=start+poz-T[poz];poz=T[poz];}
else {start=start+poz+1;poz=0;}
}
fo<<k<<'\n';
for (i=1;i<=k;i++) fo<<sol[i]<<' ';
return 0;
}