Pagini recente » Statistici Sociu Georgiana-Valentina (valentinasociu) | Istoria paginii runda/cerculdeinfo-lectia7-grafuri/clasament | Istoria paginii runda/fail | Cod sursa (job #1584551) | Cod sursa (job #1561769)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2000050
using namespace std;
char A[MAXN], B[MAXN];
int pi[MAXN], n, m, sol[1010];
void citire()
{
gets(A);
n = strlen(A);
for (int i = n; i >= 1; i--)
A[i] = A[i-1];
gets(B);
m = strlen(B);
for (int i = m; i >= 1; i--)
B[i] = B[i-1];
}
void init()
{
/// Calculam prefixele pentru A
int k = 0;
pi[1] = 0;
for (int i = 2; i <= n; i++) {
while (A[i] != A[k+1] && k)
k = pi[k];
if (A[i] == A[k+1])
k++;
pi[i] = k;
}
/// debug
// for (int i = 1; i <= n; i++)
// printf("%d ", pi[i]);
}
void newSolution(int ind)
{
sol[0]++;
if (sol[0] <= 1000)
sol[sol[0]] = ind-n+1;
}
void solve()
{
/// KMP
int k = 0;
for (int i = 1; i <= m; i++) {
while (B[i] != A[k+1] && k)
k = pi[k];
if (B[i] == A[k+1])
k++;
if (k == n)
newSolution(i);
}
}
void print()
{
printf("%d\n", sol[0]);
for (int i = 1; i <= sol[0] && i <= 1000; i++)
printf("%d ", sol[i]-1);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
init();
solve();
print();
return 0;
}