Pagini recente » Cod sursa (job #1440199) | Cod sursa (job #2701711) | Cod sursa (job #369936) | Cod sursa (job #2393713) | Cod sursa (job #1524177)
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstring>
#define maxsize 2000005
using namespace std;
std::stringstream rez;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int urm[maxsize], n, m, total;
char T[maxsize], P[maxsize];
void TheNextOne(char *P)
{
int k=-1, x;
urm[0]=0;
for (x=1; x<n; ++x)
{
while (k>0 && P[k+1]!=P[x]) k=urm[k];
if (P[k+1]==P[x]) ++k;
urm[x]=k;
}
}
int main()
{
int x=-1;
fin.getline(P,maxsize); n=strlen(P);
fin.getline(T,maxsize); m=strlen(T);
TheNextOne(P);
for (int i=0; i<m; ++i)
{
bool ok;
while (x>0&&P[x+1]!=T[i]) x=urm[x];
if (P[x+1]==T[i]) ++x; // s-au potrivit
if (x==n-1)
{
++total;
rez<<i-n+1<<' ';
if (total==1000) {ok=1;break;}
x=urm[x];
}
if (ok) break;
}
fout<<total<<'\n'<<rez.str();
return 0;
}