Pagini recente » Cod sursa (job #1026853) | Cod sursa (job #266043) | Cod sursa (job #2288618) | Cod sursa (job #341245) | Cod sursa (job #1998376)
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define Nmax 2000001
char A[Nmax], B[Nmax];
int pi[Nmax], pos[Nmax], n = 0;
void getPrefix()
{
int i = 0;
pi[0] = 0;
for( int j = 1; j<strlen(A); j++ )
{
while( i && A[i] != A[j] )
i = pi[i-1];
if( A[i] == A[j] )
i++;
pi[j] = i;
}
// for( int j = 0; j < strlen(A); j++ )
// out<<pi[j]<<'\n';
}
int main()
{
in.getline(A, Nmax);
in.getline(B, Nmax);
getPrefix();
int i = 0;
for( int j = 0; j < strlen(B); j++ )
{
while( i && A[i] != B[j])
i = pi[i-1];
if( A[i] == B[j] )
i++;
if( i == strlen(A) )
{
i = pi[i-1];
pos[++n] = j-strlen(A)+1;
}
}
out<<n<<'\n';
for( int j = 1; j<=n; j++ )
out<<pos[j]<<' ';
out<<'\n';
return 0;
}