Pagini recente » Cod sursa (job #1432642) | Cod sursa (job #170780) | Cod sursa (job #2260753) | Cod sursa (job #1372553) | Cod sursa (job #3040206)
///infoarena Potrivirea sirurilor
#include <fstream>
#include <vector>
#define SMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[SMAX], b[SMAX];
int lps[SMAX];
int k;
vector<int> rez;
int i;
int main()
{
fin >>a>>b;
k = -1; lps[0] = 0;
for (i = 1; a[i]; ++i)
{
while (k > 0 && a[k+1] != a[i]) k = lps[k];
if (a[k+1] == a[i]) k++;
lps[i] = k;
}
k = -1;
for (i = 0; b[i]; ++i)
{
while (k > 0 && a[k+1] != b[i]) k = lps[k];
if (a[k+1] == b[i]) k++;
if (!a[k+1])
{
rez.push_back(i-k);
k = lps[k];
}
}
fout <<rez.size()<<'\n';
int lim = min((int)rez.size(), 1000);
for (i = 0; i < lim; ++i)
fout <<rez[i]<<' ';
fout <<'\n';
fout.close();
return 0;
}