Pagini recente » Cod sursa (job #2428754) | Cod sursa (job #1915868) | Cod sursa (job #2484155) | Cod sursa (job #1340876) | Cod sursa (job #2174631)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
#define lenmax 2000005
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[lenmax],b[lenmax];
int len1,len2,aux[lenmax],pozcnt;
vector<int>poz;
void read()
{
f.getline(a,lenmax);
len1=strlen(a);
f.getline(b,lenmax);
len2=strlen(b);
}
void preKMP()
{
int i,j=0;
for (i=1; i<len1; ++i)
{
while (j>0&&a[i]!=a[j])
{
j=aux[j-1];
}
if (a[i]==a[j])
++j;
aux[i]=j;
}
}
void KMP()
{
int i,j=0;
for (int i=0; i<len2; ++i)
{
while (j>0&&b[i]!=a[j])
{
j=aux[j-1];
}
if (b[i]==a[j])
++j;
if (j==len1)
{
if (poz.size()==1000);
else
poz.push_back(i-len1+1);
++pozcnt;
}
}
}
void afis()
{
g<<pozcnt<<'\n';
for (auto w:poz)
g<<w<<' ';
}
int main()
{
read();
preKMP();
KMP();
afis();
return 0;
}