Pagini recente » Cod sursa (job #1912542) | Cod sursa (job #2800479) | Cod sursa (job #958391) | Cod sursa (job #2556674) | Cod sursa (job #964909)
Cod sursa(job #964909)
#include<fstream>
#include<iostream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char buff[2000000], *a, *b;
int n, m, i, *pi, 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 = 1; 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 >> buff;
n = strlen(buff);
a = new char[n + 1];
strcpy(a, buff);
fin >> buff;
m = strlen(buff);
b = new char[m + 1];
strcpy(b, buff);
pi = new int[n];
memset(pi, 0, n * sizeof(int));
calcul_functie_prefix();
kmp();
fout << r << endl;
if(r > 1000)
r = 1000;
for(i = 0; i < r; i++)
fout << raspuns[i] << " ";
return 0;
}