Pagini recente » Autentificare | Cod sursa (job #1667902) | Cod sursa (job #1104240) | Cod sursa (job #860904) | Cod sursa (job #599482)
Cod sursa(job #599482)
#include <fstream>
#include <string>
using namespace std;
#define lsir 2000000
#define mod1 200000
#define mod2 170000
#define baza 101
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[lsir], b[lsir];
int hPattern1, hPattern2, hash1, hash2, pBaza1, pBaza2, nr, poz[lsir];
int main()
{
fin >> a >> b;
int la, lb;
la = strlen(a);
lb = strlen(b);
if(la > lb)
{
fout << "0\n";
return 0;
}
pBaza1 = pBaza2 = 1;
for(int i = 0; i < la; i++)
{
hPattern1 = (hPattern1 * baza + a[i]) % mod1;
hPattern2 = (hPattern2 * baza + a[i]) % mod2;
if(i != 0)
{
pBaza1 = (pBaza1 * baza) % mod1;
pBaza2 = (pBaza2 * baza) % mod2;
}
}
for(int i = 0; i < la; i++)
{
hash1 = (hash1 * baza + b[i]) % mod1;
hash2 = (hash2 * baza + b[i]) % mod2;
}
if(hash1 == hPattern1 && hash2 == hPattern2)
{
nr++;
poz[0] = 1;
}
for(int i = la; i < lb; i++)
{
hash1 = ((hash1 - (b[i-la] * pBaza1) % mod1 + mod1) * baza + b[i]) % mod1;
hash2 = ((hash2 - (b[i-la] * pBaza2) % mod2 + mod2) * baza + b[i]) % mod2;
if(hash1 == hPattern1 && hash2 == hPattern2)
{
nr++;
poz[i - la + 1] = 1;
}
}
fout << nr << '\n';
nr = 0;
for(int i = 0; i < lb && nr < 1000; i++)
if(poz[i] == 1)
fout << i << ' ',nr++;
fout << '\n';
fin.close();
fout.close();
return 0;
}