Pagini recente » Cod sursa (job #3221260) | Cod sursa (job #820812) | Cod sursa (job #2517670) | Cod sursa (job #604961) | Cod sursa (job #2480798)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int marime = 2000005;
int prefix[marime], l1,l2, re;
vector<int>rez;
char a[marime], b[marime], c;
void create_prefix()
{
int poz;
prefix[1]=0;
for (int i=2; i<l1; ++i)
{
poz=prefix[i-1];
while (poz!=0)
{
if (a[i]==a[poz+1])
{
prefix[i]=poz+1;
break;
}
poz=prefix[poz];
}
if (poz==0)
{
if (a[1]==a[i])
prefix[i]=1;
else
prefix[i]=0;
}
}
}
void solve()
{
int ind=1;
for (int i=1; i<l2; ++i)
{
if (b[i]==a[ind])
{
ind++;
if (ind==l1)
{
ind=prefix[l1-1]+1;
rez.push_back(i-l1+1);
}
}
else
{
ind--;
while (b[i]!=a[ind+1] && ind>0)
{
ind=prefix[ind];
}
if (a[ind+1]==b[i])
ind+=2;
else
ind=1;
}
}
int marime=min(1000,rez.size());
g << rez.size() << '\n';
for (int ind=0; ind<marime; ++ind)
{
g << rez[ind] <<' ';
}
}
///ABA
///CABBCABABAB
int main()
{
l1=1;
l2=1;
f >> a+1;
f >> b+1;
l1=strlen(a+1)+1;
l2=strlen(b+1)+1;
create_prefix();
solve();
return 0;
}