Pagini recente » Cod sursa (job #2501438) | Cod sursa (job #1865947) | Cod sursa (job #273091) | Cod sursa (job #559851) | Cod sursa (job #2591839)
#include <bits/stdc++.h>
using namespace std;
ifstream f("kmp.in");
ofstream g("kmp.out");
string A,B;
int n, m, q;
int pi[20000005];
vector<int> res;
void Read()
{
f>>A>>B;
for(;(A[m] >= 'A' && A[m] <= 'Z') || (A[m] >= 'a' && A[m] <= 'z') || (A[m] >= '0' && A[m] <= '9');++m);
for(;(B[n] >= 'A' && B[n] <= 'Z') || (B[n] >= 'a' && B[n] <= 'z') || (B[n] >= '0' && B[n] <= '9');++n);
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;
}