Pagini recente » Cod sursa (job #1258894) | Cod sursa (job #3152443) | Cod sursa (job #1997003) | Cod sursa (job #932166) | Cod sursa (job #964914)
Cod sursa(job #964914)
#include<fstream>
#include<iostream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int n, m, i, pi[2000001], raspuns[1000], r;
// functia va calcula un tablou de lungimea strlen(a) (a = sirul de cautat) in care pe pozitia i se va afisa sufixul maxim
// a lui a[i] care e prefix pentru a. (a[i] = sirul format din primele i caractere ale lui a)
void calcul_functie_prefix()
{
int k = 0;
for(i = 1; i < n; i++)
{
if(k > 0 && a[i] != a[k])
k = pi[k];
if(a[i] == a[k])
k = k + 1;
pi[i] = k;
}
}
void kmp()
{
int q = 0;
for(i = 0; i < m; i++)
{
while(q > 0 && b[i] != a[q])
q = pi[q - 1];
if(b[i] == a[q])
q = q + 1;
if(q == n)
{
if(r < 1000)
raspuns[r] = i - q + 1;
r++;
q = pi[q - 1];
}
}
}
int main()
{
fin >> a;
n = strlen(a);
fin >> b;
m = strlen(b);
calcul_functie_prefix();
kmp();
fout << r << endl;
if(r > 1000)
r = 1000;
for(i = 0; i < r; i++)
fout << raspuns[i] << " ";
return 0;
}