Pagini recente » Cod sursa (job #2582550) | Cod sursa (job #967171) | Cod sursa (job #1246977) | Cod sursa (job #570626) | Cod sursa (job #1927123)
#include <fstream>
#include <cstring>
#define MAXN 2000002
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char tmp[MAXN], s[MAXN * 2];
int nn, n, k, pi[MAXN], d[1010], v[1010];
inline void Read()
{
char c;
fin >> (s + 1);
s[0] = '1';
fin >> c;
fin >> (tmp + 1);
tmp[0] = '1';
nn = strlen(s) - 1;
n = strlen(tmp) - 1;
}
inline void kmp()
{
int contor = 0;
k = 0;
pi[1] = 0;
for (int i = 2; i <= nn; i++)
{
while (k > 0 && s[i] != s[k + 1])
k = pi[k];
if (s[i] == s[k + 1])
k++;
pi[i] = k;
}
d[1] = 0;
k = 0;
if (n > 1000)
n = 1000;
for (int i = 2; i <= n; i++)
{
while (k > 0 && tmp[i] != s[k + 1])
k = pi[k];
if (s[k + 1] == tmp[i])
k++;
d[k] = k;
if (k == nn)
v[++contor] = i - nn + 1;
}
fout << contor << "\n";
for (int i = 1; i <= contor; i++)
fout << v[i] << " ";
}
int main ()
{
Read();
kmp();
fin.close(); fout.close(); return 0;
}