Pagini recente » Cod sursa (job #815461) | Cod sursa (job #357297) | Cod sursa (job #318206) | Cod sursa (job #1564115) | Cod sursa (job #1203777)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string P,T;
int URM[2000005];
vector<int> result;
int nrSol;
void prefix()
{
URM[1] = 0;
int k = 0;
for(int q=2; q<P.size(); 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.size() - 1;
nrSol = 0;
for(int i=0;i<T.size();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);
}
}
}
int main()
{
in>>P>>T;
P = '#' + P;
prefix();
match();
out<<nrSol<<'\n';
for(int i=0;i<result.size();i++)
out<<result[i]<<' ';
return 0;
}