Pagini recente » Cod sursa (job #868342) | Cod sursa (job #443344) | Cod sursa (job #806478) | Cod sursa (job #1316680) | Cod sursa (job #3333018)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX 2000001
string a, b;
int n, m, rez, lung_prefix_sufix[MAX], sol[MAX];
void constr_l_p_s()
{
int i = 1, lung_prefix = 0;
while(i < n)
{
if(a[i]==a[lung_prefix])
{
lung_prefix++;
lung_prefix_sufix[i++] = lung_prefix;
}
else
{
if(lung_prefix)
lung_prefix = lung_prefix_sufix[lung_prefix - 1];
else
lung_prefix_sufix[i++] = 0;
}
}
}
void cautare()
{
int i = 0, lung_prefix = 0;
while(i < m)
{
if(b[i] == a[lung_prefix])
{
i++;
lung_prefix++;
if(lung_prefix == n)
{
sol[++rez] = i - lung_prefix;
lung_prefix = lung_prefix_sufix[lung_prefix - 1];
}
}
else
{
if(lung_prefix)
lung_prefix = lung_prefix_sufix[lung_prefix - 1];
else
i++;
}
}
fout << rez << '\n';
if(rez > 1000)
rez = 1000;
for(int i = 1; i <= rez; i++)
fout << sol[i] << " ";
}
int main()
{
fin >> a;
fin.get();
fin >> b;
n=a.size();
m=b.size();
constr_l_p_s();
cautare();
}