Pagini recente » Cod sursa (job #2299440) | Cod sursa (job #3273955) | Cod sursa (job #624365) | Cod sursa (job #2686647) | Cod sursa (job #599481)
Cod sursa(job #599481)
#include <fstream>
#include <string>
using namespace std;
#define lsir 2000000
#define mod 100007
#define baza 73
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[lsir], b[lsir];
int hPattern, hash1, pBaza, nr, poz[lsir], la, lb;
int verifica(int start)
{
for(int i = 0; i < la; i++)
if(a[i] != b[start + i])
return 0;
return 1;
}
int main()
{
fin >> a >> b;
la = strlen(a);
lb = strlen(b);
if(la > lb)
{
fout << "0\n";
return 0;
}
pBaza = 1;
for(int i = 0; i < la; i++)
{
hPattern = (hPattern * baza + a[i]) % mod;
if(i != 0)
{
pBaza = (pBaza * baza) % mod;
}
}
for(int i = 0; i < la; i++)
{
hash1 = (hash1 * baza + b[i]) % mod;
}
if(hash1 == hPattern && verifica(0) == 1)
{
nr++;
poz[0] = 1;
}
for(int i = la; i < lb; i++)
{
hash1 = ((hash1 - (b[i-la] * pBaza) % mod + mod) * baza + b[i]) % mod;
if(hash1 == hPattern && verifica(i-la+1) == 1)
{
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;
}