Pagini recente » Cod sursa (job #1821491) | Cod sursa (job #120635) | Cod sursa (job #201457) | Cod sursa (job #2938948) | Cod sursa (job #2025649)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <set>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#define DBGVEC(v,lt,rt) {cout<<"Vector "<<(#v)<<" is: "; for(int i = lt; i <= rt; i++) cout<<v[i]<<' '; cout<<endl;}
#define DBG(x) {cout<<(#x)<<" = "<<x<<endl;}
using namespace std;
const int MAXN = 2*(1e6), a = 256, MOD = 104729;
char s1[MAXN+1], s2[MAXN+1];
long long h[MAXN+1], P, hS2;
int m, n;
vector <int> sol;
long long pwr(long long a, int n)
{
long long ans = 1;
for(int i = 1; i <= n; i++)
{
ans = ans*a;
ans %= MOD;
}
return ans;
}
long long computeh(char* s, int n)
{
long long hVal = 0, p = 1;
for(int i = n - 1; i >= 0; i--)
{
hVal += p*s[i];
hVal %= MOD;
p *= a;
p %= MOD;
}
return hVal;
}
bool compareString(char* s1, char* s2)
{
int m = strlen(s1);
for(int i = 0; i < m; i++)
if(s1[i] != s2[i])
return false;
return true;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",s1);
scanf("%s",s2);
m = strlen(s1);
n = strlen(s2);
P = pwr(a,m);
h[0] = computeh(s2,m);
hS2 = computeh(s1,m);
for(int i = 1; i <= n - m; i++)
{
h[i] = (a*h[i-1]) + (s2[i+m-1]) - (P*(s2[i-1]));
while(h[i] <= 0)
h[i] += MOD;
h[i] %= MOD;
}
for(int i = 0; i <= n-m; i++)
if(h[i] == hS2 && compareString(s1,s2+i)==true)
sol.push_back(i);
printf("%d\n",sol.size());
int toPrint = min((int)sol.size(),1000);
for(int x : sol)
{
toPrint--;
printf("%d ",x);
if(toPrint == 0)
break;
}
return 0;
}