Pagini recente » Cod sursa (job #2357982) | Cod sursa (job #787070) | Cod sursa (job #2945269) | Cod sursa (job #2566487) | Cod sursa (job #2753406)
#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[2000002];
void sufixe(int n)
{
int i, j = 0;
for (i = 1; i < n; i++)
{
while (j > 0 && t[j] != t[i])
j = suf[j - 1];
if (t[i] == t[j])
j++;
suf[i] = j;
}
}
int main()
{
int i, j, n, m, z = 0;
f.getline(t, 2000002);
f.getline(s, 2000002);
n = strlen(s);
m = strlen(t);
sufixe(m);
j = 0;
for (i = 0; i < n; i++)
{
while (j != 0 && s[i] != t[j])
{
j = suf[j - 1];
}
if (s[i] == t[j])
{
j++;
}
if (j == m)
{
if (z<=1000)
indici[++z] = i - m + 1;
j = suf[j-1];
}
}
g << z << "\n";
for (i = 1; i <= min(z,1000); i++)
{
g << indici[i] << " ";
}
return 0;
}