Pagini recente » Cod sursa (job #1695084) | Monitorul de evaluare | Cod sursa (job #552613) | Cod sursa (job #1567418) | Cod sursa (job #2387712)
#include <fstream>
#include <cstring>
#define MAX 2000004
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int q1, q2, j, gasit, sol[MAX], pattern[MAX];
char A[MAX], B[MAX];
int main()
{
cin.getline(A, MAX);
cin.getline(B, MAX);
q1 = strlen(A);
q1--;
q2 = strlen(B);
q2--;
j = 0;
for(int i=1; i <= q1; i++)
{
while(A[i] != A[j] && j > 0)
j = A[j-1];
if(A[i] == A[j])
j++;
pattern[i] = j;
}
j=1;
for(int i=0; i <= q2; i++)
{
while(B[i] != A[j] && j > 0)
{
j = pattern[j-1];
}
if(B[i] == A[j])
{
j++;
}
if(j == q1+1)
{
gasit++;
sol[gasit] = i-j+1;
}
}
cout << gasit << '\n';
for(int i=1; i <= gasit; i++)
{
cout << sol[i] << ' ';
}
}