Pagini recente » Cod sursa (job #2163098) | Cod sursa (job #218255) | Cod sursa (job #3151789) | Cod sursa (job #2181609) | Cod sursa (job #1627683)
#include <cstring>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define N 2000000
char A[1 + N], B[1 + N];
int n, m;
int pred[1 + N];
int rez[1 + N], nr = 0;
inline void construiestePred()
{
int i, k = 0;
for(int i = 2; i <= n; i++)
{
while(k != 0 && A[i] != A[1 + k])
k = pred[k];
if(A[i] == A[1 + k])
k++;
pred[i] = k;
}
return;
}
inline void cautaInB()
{
int i, k = 0;
for(int i = 2; i <= m; i++)
{
while(k != 0 && B[i] != A[1 + k])
k = pred[k];
if(B[i] == A[1 + k])
k++;
if(k == n)
rez[++nr] = i - n;
}
return;
}
inline void afiseaza()
{
out << nr << '\n';
if(nr > 1000)
nr = 1000;
for(int i = 1; i <= nr; i++)
out << rez[i] << ' ';
}
int main()
{
in >> (1 + A) >> (1 + B);
n = strlen(1 + A);
m = strlen(1 + B);
construiestePred();
cautaInB();
afiseaza();
return 0;
}