Pagini recente » Cod sursa (job #1410013) | Cod sursa (job #1224515) | Cod sursa (job #1737435) | Cod sursa (job #728238)
Cod sursa(job #728238)
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=2000005;
char t[maxn], p[maxn];
int l,n,m,x,nr;
int urm[maxn];
vector<int>poz;
void urmatorul(char *p)
{
//urm[k] cate litere din sufixul lui p[0..k] sunt prefixul lui P
int lung;
lung=-1;
urm[0]=-1;
n=strlen(p);
for(x=1;x<n;x++) // parcurg prefixele de lungime x P[0..x]
{
//cattimp k>0 (lung este cate litere se potrivesc)
while(lung>0 && p[lung+1]!=p[x])
lung=urm[lung]; // eu stiu ca am potrivit lung litere din p
//
if(p[lung+1]==p[x])
lung++;
urm[x]=lung;
}
}
int cmp(int a, int b)
{
return a>b?0:1;
}
int main()
{
int i;
int x=-1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(p,maxn);
f.getline(t,maxn);
n=strlen(p);
m=strlen(t);
//m--;
//n--;
urmatorul(p);
nr=0;
for(i=0;i<m;i++)
{
while(x>0 && p[x+1]!=t[i])
x=urm[x];
if(p[x+1]==t[i])
x++;
if(x==n-1) //sirurile s-au potrivit
{nr++;
poz.push_back(i-n+1);
x=urm[x];
}
}
g<<nr<<"\n";
sort(poz.begin(), poz.end(), cmp);
if (nr>1000) nr=1000;
for(i=0;i<nr;i++)
g<<poz[i]<<" ";
return 0;
}