Cod sursa(job #192832)

Utilizator raduzerRadu Zernoveanu raduzer Data 31 mai 2008 18:37:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>   
#include <string.h>   
  
int n,m,k,i,j,t,a[2000005],b[2000005],q,c[1005];  
char x,s[2000003];   
  
int main()   
{   
    freopen("strmatch.in","r",stdin);   
    freopen("strmatch.out","w",stdout);   
	fgets(s,2000002,stdin);
	k=strlen(s)-1;
	for (i=1; i<=k; ++i)
	{
		if (s[i-1]>='0' && s[i-1]<='9') b[i]=b[i-1]+(s[i-1]-'0');   
		if (s[i-1]>='A' && s[i-1]<='Z') b[i]=b[i-1]+(s[i-1]-'A')+10;   
		if (s[i-1]>='a' && s[i-1]<='z') b[i]=b[i-1]+(s[i-1]-'a')+10+26;   
	}
	fgets(s,2000002,stdin);
	n=strlen(s)-1;
	for (i=1; i<=n; ++i)
	{
        if (s[i-1]>='0' && s[i-1]<='9') a[i]=a[i-1]+(s[i-1]-'0');   
        if (s[i-1]>='A' && s[i-1]<='Z') a[i]=a[i-1]+(s[i-1]-'A')+10;   
        if (s[i-1]>='a' && s[i-1]<='z') a[i]=a[i-1]+(s[i-1]-'a')+10+26;   
    }   
    int sol=0;   
    for (i=k; i<=n; ++i)   
        if (b[k]==a[i]-a[i-k])   
        {   
            q=1;   
            for (j=1; j<=k; ++j) if (b[j]!=a[i-k+j]-a[i-k]) { q=0; break; }   
            if (q) ++sol;   
            if (q && sol<=1000) c[sol]=i-k;   
        }   
    printf("%d\n",sol);   
	for (i=1; i<=sol; ++i) { if (i>1000) break; printf("%d ",c[i]); }
    return 0;   
}