Pagini recente » Cod sursa (job #598768) | Cod sursa (job #2216174) | Cod sursa (job #1663503) | Cod sursa (job #21914) | Cod sursa (job #2753429)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <climits>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[2000002], t[2000002];
int suf[2000002], indici[1001];
void asezare(int n, char s[])
{
int i;
for (i = n; i > 0; i--)
s[i] = s[i - 1];
s[0] = 0;
}
void sufixe(int n)
{
int i, j = 0;
for (i = 2; i <= n; i++)
{
j = suf[i - 1];
while (j > 0 && t[j+1] != t[i])
j = suf[j];
if (j > 0 || t[i] == t[j+1])
suf[i] = j + 1;
}
}
int main()
{
int i, j, n, m, z = 0;
f.getline(t, 2000002);
f.getline(s, 2000002);
n = strlen(s);
m = strlen(t);
asezare(m,t);
asezare(n,s);
sufixe(m);
j = 0;
for (i = 1; i <= n; i++)
{
while (j != 0 && s[i] != t[j+1])
{
j = suf[j];
}
if (s[i] == t[j+1])
{
j++;
}
if (j == m)
{
z++;
if (z <= 1000)
indici[z] = i - m;
j = suf[m];
}
}
g << z << "\n";
for (i = 1; i <= min(z, 1000); i++)
{
g << indici[i] << " ";
}
return 0;
}