Pagini recente » Cod sursa (job #2567767) | Cod sursa (job #1343422) | Cod sursa (job #2980289) | Cod sursa (job #517901) | Cod sursa (job #2983465)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int k, poz[2000005];
int lps[2000005];
void generare_lps()
{
int n = A.size();
int j = 0;
for(int i = 1; i < n; i++)
{
while(j > 0 && A[j] != A[i])
j = lps[j - 1];
if(A[j] == A[i])
j++;
lps[i] = j;
}
}
void KMP()
{
generare_lps();
int n = B.size();
int m = A.size();
int j = 0;
for(int i = 0; i < n; i++)
{
while(j > 0 && A[j] != B[i])
j = lps[j - 1];
if(A[j] == B[i])
j++;
if(j == m)
{
poz[k++] = i - m + 1;
j = lps[j - 1];
}
}
}
int main()
{
fin >> A >> B;
KMP();
fout << k << '\n';
if(k <= 1000)
{
for(int i = 0; i < k; i++)
fout << poz[i] << ' ';
}
else
{
for(int i = 0; i < 1000; i++)
fout << poz[i] << ' ';
}
return 0;
}