Pagini recente » Cod sursa (job #1567683) | Cod sursa (job #1175178) | Cod sursa (job #1172136) | Istoria paginii runda/tp3 | Cod sursa (job #2591837)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
int n, m, q;
int pi[20000005];
vector<int> res;
void Read()
{
cin>>A>>B;
m = A.length();
n = B.length();
A.insert(0, " ");
B.insert(0, " ");
f.close();
}
void compute()
{
q = 0;
pi[0] = 1;
for(int i = 2;i <= m;++i)
{
while(q > 0 && A[q + 1] != A[i])
q = pi[q];
if(A[q + 1] == A[i])
++q;
pi[i] = q;
}
}
void KMP()
{
q = 0;
for(int i = 1;i <= n;++i)
{
while(q > 0 && A[q + 1] != B[i])
q = pi[q];
if(A[q + 1] == B[i])
++q;
if(q == m)
{
q = pi[q];
if(res.size() < 1000)
res.push_back(i - m);
}
}
}
void Print()
{
g<<res.size()<<'\n';
for(vector<int>::iterator it = res.begin();it != res.end();++it)
g<<*it<<" ";
g.close();
}
int main()
{
Read();
compute();
KMP();
Print();
return 0;
}