Pagini recente » Borderou de evaluare (job #2994661) | Borderou de evaluare (job #3034163) | Borderou de evaluare (job #1143839) | Borderou de evaluare (job #3098354) | Cod sursa (job #922501)
Cod sursa(job #922501)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int Nmax = 2000010;
typedef unsigned long long I64;
const int B1 = 73;
const int B2 = 79;
I64 V1,V2;int N;
I64 W1,W2;int M;
I64 P1 = 1LL;
I64 P2 = 1LL;
char A[Nmax],B[Nmax];
vector<int> V;int Co;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
void Count(int i)
{
++Co;
if ( V.size() < 1000 )
V.push_back( i );
}
int main()
{
F.getline(A,Nmax,'\n'), N = strlen(A);
F.getline(B,Nmax,'\n'), M = strlen(B);
for (int i=0;i<N;++i)
V1 = ( V1 * B1 ) + A[i],
V2 = ( V2 * B2 ) + A[i];
for (int i=1;i<N;++i)
P1 *= B1,
P2 *= B2;
for (int i=0;i<N;++i)
W1 = ( W1 * B1 ) + B[i],
W2 = ( W2 * B2 ) + B[i];
if ( W1 == V1 && W2 == V2 ) Count(0);
for (int i=N;i<M;++i)
{
W1 = ( W1 - ( B[i-N] * P1 ) ) * B1 + B[i];
W2 = ( W2 - ( B[i-N] * P2 ) ) * B2 + B[i];
if ( W1 == V1 && W2 == V2 ) Count(i-N+1);
}
G<<Co<<'\n';
for (int i=0;i<int(V.size());++i)
G<<V[i]<<' ';
G<<'\n';
}