Pagini recente » Cod sursa (job #956432) | Cod sursa (job #3246402) | Cod sursa (job #1560795) | Cod sursa (job #544329) | Cod sursa (job #1519716)
#include <fstream>
#include <cstring>
#define mod1 10007
#define mod2 666013
#define factor 123
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int Nmax = 2000010;
char str1[Nmax], str2[Nmax];
int match[1001];
int N, M;
int vstr1mod1, vstr1mod2;
int vstr2mod1, vstr2mod2;
int putere1, putere2;
int contor;
int x, y;
int main ()
{
f.get(str1, sizeof(str1));
f.get();
f.get(str2, sizeof(str2));
N = strlen(str1);
M = strlen(str2);
putere1 = putere2 = 1;
for(int i = 0; i < N; i ++)
{
vstr1mod1 = (vstr1mod1 * factor + str1[i]) % mod1;
vstr1mod2 = (vstr1mod2 * factor + str1[i]) % mod2;
if(i != 0)
{
putere1 = (putere1 * factor) %mod1;
putere2 = (putere2 * factor) %mod2;
}
}
for(int i = 0; i < N; i ++)
{
vstr2mod1 = (vstr2mod1 * factor + str2[i]) % mod1;
vstr2mod2 = (vstr2mod2 * factor + str2[i]) % mod2;
}
if(vstr1mod1 == vstr2mod1 && vstr1mod2 == vstr2mod2) { contor ++; match[contor] = 0; }
for(int i = N; i < M; i ++)
{
x = (putere1 * str2[i - N]) % mod1;
y = (putere2 * str2[i - N]) % mod2;
vstr2mod1 -= x;
vstr2mod2 -= y;
if(vstr2mod1 < 0) vstr2mod1 += mod1;
if(vstr2mod2 < 0) vstr2mod2 += mod2;
vstr2mod1 = (vstr2mod1 * factor + str2[i]) % mod1;
vstr2mod2 = (vstr2mod2 * factor + str2[i]) % mod2;
if(vstr1mod1 == vstr2mod1 && vstr1mod2 == vstr2mod2) { contor ++; if(contor < 1000) match[contor] = i - N + 1; }
}
g << contor << '\n';
for(int i = 0; i < 1001; i ++) if(match[i] != 0) g << match[i] << ' ';
g << '\n';
return 0;
}