Pagini recente » Cod sursa (job #1632060) | Cod sursa (job #1874249) | Cod sursa (job #2301959) | Cod sursa (job #322827) | Cod sursa (job #2817474)
#include <bits/stdc++.h>
#define n_max 100001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int lena, lenb;
int pi[2000001];
void read()
{
f>>a;
lena = a.length(); a.insert(0, " ");
f>>b;
lenb = b.length(); b.insert(0, " ");
}
void compute()
{
int q = 0;
for(int i = 2;i <= lena;++i)
{
while(q && a[q + 1] != a[i])
q = pi[q];
if(a[q + 1] == a[i])
q++;
pi[i] = q;
}
}
void solve()
{
compute();
vector<int> result;
int number = 0, q = 0;
for(int i = 1;i <= lenb;++i)
{
while(q && a[q + 1] != b[i])
q = pi[q];
if(a[q + 1] == b[i])
q++;
if(q == lena)
{
++number;
q = pi[q];
if(number <= 1000)
result.push_back(i - lena);
}
}
g<<number<<'\n';
for(int position : result)
g<<position<<" ";
}
int main()
{
read();
solve();
return 0;
}