Pagini recente » Istoria paginii runda/oji_simulare_2018_cl10/clasament | Cod sursa (job #522969) | Diferente pentru utilizator/teofilos intre reviziile 24 si 21 | Diferente pentru utilizator/teofilos intre reviziile 22 si 23 | Cod sursa (job #156656)
Cod sursa(job #156656)
#include <fstream>
#include <cstring>
#define MAX 2000001
#define mini(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int m, n, sol[1001], nr = 0, pi[MAX];
char a[MAX], x[MAX];
void KMP();
void Prefix();
int main()
{
int i;
ifstream fin("strmatch.in");
fin >> x;
fin >> a;
fin.close();
n = strlen(x);
for (i = n; i; i--)
x[i] = x[i-1];
x[0] = ' ';
m = strlen(a);
for (i = m; i; i--)
a[i] = a[i-1];
a[0] = ' ';
KMP();
ofstream fout("strmatch.out");
fout << nr << "\n";
for (i = 1; i <= mini(nr, 1000); i++)
fout << sol[i] << " ";
fout.close();
return 0;
}
void Prefix()
{
int i, k;
k = 0;
pi[1] = 0;
for (i = 2; i <= n; i++)
{
while (x[i] != x[k+1] && k) {k = pi[k];}
if (x[i] == x[k+1]) k++;
pi[i] = k;
}
}
void KMP()
{
int i, k;
Prefix();
k = 0;
for (i = 1; i <= m; i++)
{
while (x[k+1] != a[i] && k) {k = pi[k];}
if (a[i] == x[k+1]) k++;
if (k == n)
{
++nr;
if (nr <= 1000)
sol[nr] = i-n;
k = pi[k];
}
}
}