Pagini recente » Cod sursa (job #2746634) | Cod sursa (job #122811) | Cod sursa (job #2886767) | Borderou de evaluare (job #853670) | Cod sursa (job #2732609)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lps[2000001];
inline void getLPS(const string& a)
{ int j, i;
j=0;
for (i=1;i<a.size();)
if (a[i]==a[j])
{ ++j;
lps[i]=j;
++i;
}
else
if (j)
j=lps[j-1];
else
++i;
}
inline void getMatches(const string& a, const string& b)
{ vector<int> pos;
int cnt, i, j;
cnt=0;
pos.reserve(1000);
for (i=j=0;i<b.size();)
{ if (a[j]==b[i])
++i, ++j;
else
if (j)
j=lps[j-1];
else
++i;
if (j==a.size())
{ ++cnt;
if (pos.size()<1000)
pos.push_back(i-j);
j=lps[j-1];
}
}
fout<<cnt<<'\n';
for (i=0;i<pos.size();++i)
fout<<pos[i]<<' ';
}
int main()
{ ios::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
string a, b;
fin>>a>>b;
fin.close();
getLPS(a);
getMatches(a, b);
fout.close();
return 0;
}