Pagini recente » Cod sursa (job #1780925) | Cod sursa (job #2817567) | Cod sursa (job #1542829) | Cod sursa (job #2432336) | Cod sursa (job #1276134)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define N 2000002
#define P 191LL
#define mod 6074001001LL
char substr[N],str[N];
int main ()
{
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
fscanf(fin,"%s %s", substr, str);
long long int hash_substr = 0LL;
int len = strlen(substr);
long long int P_len = 1LL;
for(int i=0;i<len; i++)
{
hash_substr = (hash_substr * P + substr[i]) % mod;
P_len = (P_len * P) % mod;
}
long long int hash_str=0;
int i;
for(i=0;i<len;i++)
{
hash_str = (hash_str*P + str[i]) % mod;
}
std::vector<int> v;
for(;i<strlen(str);i++)
{
if(hash_str==hash_substr)
{
int flag = true;
v.push_back(i-len);
/*
for(int j=0;j<len;j++)
{
if(substr[j] != str[i+j-len])
{
flag=false;
}
}
if(flag)
{
}
*/
}
hash_str = (hash_str * P + str[i] - P_len*str[i - len]) % mod;
}
fprintf(fout, "%d\n", v.size());
for(auto& e: v)
{
fprintf(fout, "%d ", e);
}
return 0;
}