Pagini recente » Cod sursa (job #2171519) | Cod sursa (job #2174056) | Cod sursa (job #1296257) | Cod sursa (job #1690150) | Cod sursa (job #1844359)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define lim 2000100
char pattern[lim],text[lim],sum[2*lim],nr;
int pref[2*lim];
int n,m,l;
vector <int> v;
void formare()
{
strcat(sum,".");
strcat(sum,pattern);
strcat(sum,"*");
strcat(sum,text);
n=strlen(pattern);
m=strlen(text);
l=strlen(sum)-1;
}
void prefix_function()
{
int k;
for(int i=2; i<=l; i++)
{
k=pref[i-1];
while(k && sum[k+1]!=sum[i]) k=pref[k];
if(sum[k+1]==sum[i]) k++;
pref[i]=k;
if(k==n && i>n+1) v.push_back(i-2*n-1);
}
}
void afisare()
{
fout<<v.size()<<'\n';
for(auto it:v)
{
fout<<it<<' ';
if(++nr==1000) return;
}
}
int main()
{
fin>>pattern>>text;
formare();
prefix_function();
afisare();
fin.close();
fout.close();
return 0;
}