Pagini recente » Cod sursa (job #473929) | Cod sursa (job #2457335) | Cod sursa (job #1409333) | Cod sursa (job #70166) | Cod sursa (job #1301799)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream f1("strmatch.in");
ofstream f2("strmatch.out");
#define MX 2000010
int n,m, c[MX], nc ; // c - coada solutiilor
char a[MX],b[MX];
unsigned int f_hash_sm(char s[], int st, int dr )
{
unsigned int v=0;
for (int i=st; i<=dr; i++ )
v+= s[i];
return v;
}
int verifica(char s1[], int n, char s2[], int st )
{
for (int i=0; i<=n; i++)
if (s1[i] != s2[st+i] ) return 0;
return 1;
}
void cauta_ap(char s1[], int n, char s2[], int m )
{
unsigned int v1= f_hash_sm(s1,0,n), v=f_hash_sm(s2,0,n) ;
for (int i=n ; i<=m; i++ )
{
if (v==v1 )
if (verifica(s1,n,s2,i-n ) )
c[++nc]=i-n;
v= v- s2[i-n] + s2[i+1];
}
}
int main()
{
f1>>a;
f1>>b;
n=strlen(a);
m=strlen(b);
if (n>m) {f2<<0; return 0; } // cazul imposibilitatii
cauta_ap(a,n-1,b,m-1);
f2<<nc<<"\n";
for (int i=1; i<=min(nc,1000) ; i++)
f2<<c[i]<<" ";
f2.close();
return 0;
}