Pagini recente » Cod sursa (job #1282983) | Cod sursa (job #207431) | Cod sursa (job #2273808) | Cod sursa (job #606684) | Cod sursa (job #1897052)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#define nmax 2000002
#define mmax 2000002
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,2000001);
f.getline(t,2000001);
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;
}