Pagini recente » Cod sursa (job #2067374) | Cod sursa (job #2089771) | Cod sursa (job #3209018) | Cod sursa (job #2739770) | Cod sursa (job #1804900)
#include<bits/stdc++.h>
#define NMAX 2000040
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[NMAX], sol[NMAX], s, n, m;
char a[NMAX], b[NMAX];
int main ()
{
f>> a + 1 >> b + 1;
n = strlen (a + 1);
m = strlen (b + 1);
int k = 0;
for (int i = 2; i <= n; i++)
{
while (k && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
k++;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= m; i++)
{
while (k && a[k + 1] != b[i])
k = pi[k];
if (a[k + 1] == b[i])
k++;
if (k == n)
{
s++;
if (s <= 1000)
sol[s] = i - k;
k = pi[k];
}
}
g<< s << "\n" ;
for (int i = 1; i <= min (1000,s); i++)
g<< sol[i] << " ";
return 0;
}