Pagini recente » Cod sursa (job #100643) | Cod sursa (job #1381744) | Cod sursa (job #697508) | Cod sursa (job #3150936) | Cod sursa (job #2354741)
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000005];
char A[2000005], B[2000005];
int n, m;
void prefix() //CALCUL FUNCTIE PREFIX
{
int k = 0;
pi[1] = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 and A[k + 1] != A[i])
k = pi[k];
if (A[k + 1] == A[i])
k++;
pi[i] = k;
}
}
int main()
{
fin.getline(A+1,2000005);
fin.getline(B+1,2000005); cout << A << B;
n = strlen(A+ 1) ; m = strlen(B+ 1) ;
int v[2000];
int NR = 0;
prefix();
// POTRIVIRE KMP
int q = 0;
for (int i = 1; i <= m; i++) {
while (q > 0 and A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
q++;
if (q == n)
if(n<1000)
v[++NR] = i - n;
else ++NR;
}
fout << NR <<"\n";
for (int i = 1; i <= min(NR, 1000); i++)
fout << v[i]<<" ";
}