Pagini recente » Cod sursa (job #273405) | Cod sursa (job #236139) | Cod sursa (job #2249648) | Cod sursa (job #1008140) | Cod sursa (job #1527869)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define LMax 2000005
#define P 317
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[LMax], B[LMax];
int n, m;
unsigned long long h1, h2, PP = 1LL;
vector<int> sol;
int main()
{
f>>A>>B;
n = strlen(A);
m = strlen(B);
int i;
for(i=0;i<n;++i) h1 = h1 * P + A[i], h2 = h2 * P + B[i];
for(i=1;i<n;++i) PP *= P;
if(h1 == h2) sol.push_back(1);
for(i=n;i<m;++i)
{
h2 -= B[i-n] * PP;
h2 = h2 * P + B[i];
if(h1 == h2) sol.push_back(i-n+1);
}
g<<sol.size()<<"\n";
int x = min(1000, (int)sol.size());
for(i=0;i<x;++i) g<<sol[i]<<" ";
f.close();
g.close();
return 0;
}