Pagini recente » Cod sursa (job #2801504) | Cod sursa (job #1083428) | Cod sursa (job #48765) | Cod sursa (job #2634641) | Cod sursa (job #1793315)
#include <fstream>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
//#include <unordered_map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
#include <bitset>
#include <map>
#define MAX 500000000000
//#include <iostream>
//#include <windows.h>
#include <deque>
using namespace std;
//ifstream cin("jocul.in");
//ofstream cout("jocul.out");
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int val = 0, prime = 61, index = 1;
int hash_cal(string p)
{
for(int i = 0; i < p.size(); i++)
{
val += index * (p[i] - 52);
index *= prime;
}
return val;
}
void recalc_hash(string p, vector<int> &x, int indexx)
{
int sum = 1, val = 0;
for(int i = 0; i <= indexx; i++)
{
val += (sum * (p[i] - 52));
sum *= prime;
}
sum /= 61;
x.push_back(val);
for(int i = indexx + 1; i < p.size(); i++)
{
int curr = (val - (p[i - indexx - 1] - 52));
curr /= 61;
curr += (p[i] - 52) * sum;
val = curr;
x.push_back(curr);
}
}
int main()
{
string s, p;
cin >> s >> p;
int valor = hash_cal(s);
vector<int> x, y;
recalc_hash(p, x, s.size() - 1);
for(int i = 0; i < x.size(); i++)
if(x[i] == valor)
y.push_back(i);
cout << y.size() << "\n";
for(int i = 0; i < y.size(); i++)
cout << y[i] << " ";
return 0;
}