Pagini recente » Cod sursa (job #1956951) | Cod sursa (job #3127926) | Cod sursa (job #3176787) | Cod sursa (job #2968163) | Cod sursa (job #2879841)
#include <fstream>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
string a, b;
vector <int> rez;
fin >> a;
fin >> b;
int nrlitalfabet = 26, prim = 163487, lung = a.length(), i, j;
long long putere = 1, hasha=0, putmic = 1, hashb = 0, hashbnou;
for (i = 0; i < lung-1; i++)
{
putere = ((putere /*% prim*/) * nrlitalfabet) /*% prim*/;
}
if (a.length() > b.length())
fout << 0;
else
{
for(i = lung-1; i >=0 ; i--)
{
hasha = (hasha + ((putmic % prim) * (tolower(a[i])-'a'+1)))%prim;
hashb = (hashb + ((putmic % prim) * (tolower(b[i])-'a'+1))) % prim;
putmic = (putmic * nrlitalfabet) % prim;
}
if (hasha == hashb)
rez.push_back(0);
hashbnou = hashb;
for (i = lung; i < b.length(); i++)
{
j = i - lung + 1;
hashbnou = (((hashbnou - (((tolower(b[j-1])-'a'+1) * putere)%prim))*nrlitalfabet) + (tolower(b[i])-'a'+1))%prim;
if (hashbnou == hasha)
rez.push_back(j);
}
}
fout << rez.size() << '\n';
for (auto i : rez)
fout << i << ' ';
return 0;
}