Pagini recente » Cod sursa (job #3267043) | Cod sursa (job #2720497) | Cod sursa (job #2582980) | Cod sursa (job #805444) | Cod sursa (job #1201928)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string P,T;
int URM[2000005];
vector<int> result;
int nrSol;
void prefix();
void match();
void print();
int main()
{
fin>>P>>T;
P = '#' + P;
prefix();
match();
print();
return 0;
}
void prefix()
{
URM[1] = 0;
int k = 0;
for(int q=2; q<P.length(); q++)
{
while(k > 0 && P[k + 1] != P[q])
{
k = URM[k];
}
if(P[k + 1] == P[q])
{
k = k + 1;
}
URM[q] = k;
}
}
void match()
{
int q = 0;
int m = P.length() - 1;
nrSol = 0;
for(int i=0;i<T.length();i++)
{
while(q > 0 && P[q + 1] != T[i])
{
q = URM[q];
}
if(P[q + 1] == T[i])
{
q = q + 1;
}
if(q == m)
{
++nrSol;
if(nrSol<=1000)
{
result.push_back(i - m + 1);
}
}
}
}
void print()
{
fout<<nrSol<<'\n';
for(int i=0;i<result.size();i++)
{
fout<<result[i]<<' ';
}
}