Cod sursa(job #1487613)

Utilizator LurchssLaurentiu Duma Lurchss Data 17 septembrie 2015 09:41:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <string.h>

#define nmax 2000002
using namespace std;

char s[nmax],pattern[nmax];
int n,m;
int sol[nmax];
vector<int> v;
void read()
{
    scanf("%s\n",&pattern);
    scanf("%s",&s);
    n=strlen(s);
    m=strlen(pattern);
}

int Hash(char ss[nmax])
{
    int value=0;
    for(int i=0;i<m;i++)
        value+=ss[i];
    return value;
}

void solve()
{
    int hs,hpattern;
    hs=Hash(s);
    hpattern=Hash(pattern);
    for(int i=0;i<n-m+1;i++)
        {
            if(hs == hpattern)
            {
                int ok=1;
                for(int j=0;j<m;j++)
                if(s[i+j]!=pattern[j])
                    {ok=0;
                    break;}
                if(ok)
                    v.push_back(i);
            }
            hs = hs - s[i]+s[i+m];
        }
    printf("%d\n",v.size());
    int sol = v.size()<1000?v.size():1000;
    for(int i=0;i<sol;i++)
        printf("%d ",v[i]);
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    read();
    solve();
    return 0;
}