Pagini recente » Cod sursa (job #2799717) | Cod sursa (job #1396152) | Cod sursa (job #1707216) | Cod sursa (job #1620403) | Cod sursa (job #2732259)
#include <bits/stdc++.h>
#define N 2000008
#define mod 1000000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[N];
char b[N];
long long H[2][N];
int n, m;
void Citire()
{
fin >> a;
n = strlen( a );
fin >> b;
m = strlen( b );
}
long long P[N];
void createHash()
{
int i;
H[0][0] = a[0];
for( i=1; i<n; i++ )
H[0][i] = ( ( H[0][i - 1] * 26 ) % mod + a[i] ) % mod;
H[1][0] = b[0];
for( i=1; i<m; i++ )
H[1][i] = ( ( H[1][i - 1] * 26 ) % mod + b[i] ) % mod;
}
vector<int> sol;
void Rezolvare()
{
int i;
P[0] = 1;
for( i=1; i<=max( n, m ); i++ )
P[i] = ( P[i - 1] * 26 ) % mod;
createHash();
if( n > m )
{
fout << "0";
return;
}
int ct = 0;
for( i=n - 1; i<m; i++ )
{
long long Hash = ( H[1][i] + mod - ( (i - n < 0 ? 0 : H[1][i - n]) * P[n] ) % mod ) % mod;
if( H[0][n-1] == Hash ) ct++, sol.push_back( i - n + 1 );
}
fout << ct << "\n";
ct = 0;
for( auto e : sol )
{
ct++;
if( ct > 1000 ) return;
fout << e << " ";
}
}
int main()
{
Citire();
Rezolvare();
fin.close();
fout.close();
return 0;
}