Pagini recente » Cod sursa (job #3294530) | Monitorul de evaluare | Cod sursa (job #3258220) | Profil moga_florian | Cod sursa (job #2482449)
#include <bits/stdc++.h>
#define NMAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> sol;
string a, b;
int lghA, lghB;
int prefix[NMAX];
void make_prefix()
{
int q = 0;
prefix[1] = 0;
for(int i=2; i<lghA; i++)
{
while(q!=0 && a[q+1] != a[i])
q = prefix[q];
if(a[q+1] == a[i])
q++;
prefix[i] = q;
}
}
void showPrefix()
{
fout << "prefix: ";
for(int i=1; i<lghA; i++)
fout << prefix[i] << ' ';
fout << '\n';
}
int main()
{
fin >> a >> b;
a = "#" + a;
b = "#" + b;
lghA = a.size();
lghB = b.size();
make_prefix();
//fout << a << '\n';
//showPrefix();
//fout << b << '\n';
int q = 0;
for(int i=1; i<lghB; i++)
{
while(q!=0 && a[q+1] != b[i])
q = prefix[q];
if(a[q+1] == b[i])
q++;
if(q == lghA - 1){
sol.push_back(i);
q = prefix[q];
}
}
fout << sol.size() << '\n';
int afisari = 0;
for(auto it:sol){
afisari ++;
if(afisari <= 1000)
fout << it-lghA+1 << ' ';
}
return 0;
}