Pagini recente » Cod sursa (job #2597800) | Cod sursa (job #317162) | Cod sursa (job #275901) | Cod sursa (job #2725472) | Cod sursa (job #1968358)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#define nmax 2000011
#define mmax 2000011
using namespace std;
char t[nmax], p[nmax];
int urm[nmax];
int n, m;
vector <int> poz;
void urmatorul(char *p)
{
int k=-1, x;
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;
}
}
int main()
{
int i, x=-1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(p,2000005);
f.getline(t,2000005);
n=strlen(t);
m=strlen(p);
urmatorul(p);
for (i=1; i<=n; ++i)
for (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) poz.push_back(i-m+1);
}
g << poz.size() << "\n";
vector <int> :: iterator it;
for (it=poz.begin();it!=poz.end();++it)
if (distance(poz.begin(),it) <1000) g << *it << " ";
else break;
return 0;
}