Cod sursa(job #1004944)

Utilizator thewildnathNathan Wildenberg thewildnath Data 3 octombrie 2013 20:41:23
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

char a[2000002],b[2000002];
vector <int> s[1000002];
vector <int> poz;

int main()                                    //Sursa proasta ;)
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int n,m,i,j,sol=0,k;
    scanf("%s%s",&a,&b);
    n=strlen(a);
    m=strlen(b);
    ///////////////////////////
    i=0;
    while(b[i]!=a[0])
        ++i;
    if(i==m)
    {
        printf("0\n");
        return 0;
    }
    s[i].push_back(1);
    ++i;
    if(n==1)
    {
        ++sol;
        poz.push_back(i);
    }
    //////////////////////////
    for(;i<m;++i)
    {
        k=s[i-1].size();
        s[i].push_back(0);
        for(j=0;j<k;++j)
        {
            if(b[i]==a[s[i-1][j]])
            {
                if(s[i-1][j]==n-1)
                {
                    ++sol;
                    poz.push_back(i-n+1);
                }
                else
                    s[i].push_back(s[i-1][j]+1);
            }
        }
    }
    printf("%d\n",sol);
    if(sol>1000)
        sol=1000;
    for(i=0;i<sol;++i)
        printf("%d ",poz[i]);
    printf("\n");
    return 0;
}