Pagini recente » Cod sursa (job #1355541) | Istoria paginii runda/qwerty-2 | Cod sursa (job #3227448) | Cod sursa (job #2433881) | Cod sursa (job #2591832)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch");
ofstream g("strmatch");
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[1] = 0;
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;
}