Pagini recente » Cod sursa (job #1448096) | Cod sursa (job #2088988) | Cod sursa (job #404316) | Cod sursa (job #2989311) | Cod sursa (job #1402213)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <string>
#define DMAX 2000050
using namespace std;
char P[DMAX],T[DMAX];
int urm[DMAX];
vector<long > solutii;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> P >> T;
long long n,m,k,x;
n=strlen(T),m=strlen(P);
//cout << n << " " << m;
k=-1,x=0;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0 && P[k+1]!=P[x]) k=urm[k];
if(P[k+1]==P[x]) k++;
urm[x]=k;
}
x=-1;
for(long long i=0;i<n;i++)
{
while(x>0 && P[x+1]!=T[i]) x=urm[x];
if(P[x+1]==T[i]) x++;
if(x==m-1)
{
solutii.push_back(i-m+1);
x=urm[x];
}
}
int nr=1000;
if(solutii.size()<1000) nr=solutii.size();
out << solutii.size() << "\n";
for(long long i=0;i<nr;i++)
out << solutii[i] << " ";
return 0;
}