Cod sursa(job #1441956)

Utilizator RazvanSSavu Razvan RazvanS Data 24 mai 2015 13:47:25
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.37 kb
/* 
 * File:   main.c
 * Author: Razvan
 *
 * Created on May 24, 2015, 12:24 PM
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FILE_IN "strmatch.in"
#define FILE_OUT "strmatch.out"

#define STR_SIZE 1<<21
#define MAX_PRINT 1000
#define MIN(a,b) a <= b ? a : b;

char word[STR_SIZE], line[STR_SIZE];
int i, T[STR_SIZE], wl, ll, M[STR_SIZE], mc;

void computeT(void)
{
    T[0] = 0;
    T[1] = 1;
    for(i=2;i<=wl;++i)
        for(T[i] = T[i-1];T[i] <= i-1 && word[i-1] != word[i-1-T[i]];T[i]++);
}

void findMatches(void)
{
    int lp=0, wp=0;
    while (lp<ll)
    {
//        printf("%d %d\n", lp, wp);
        if(wp < wl && line[lp] == word[wp])
        {
            if (wp == wl-1)
            {
                M[mc++] = lp - wl + 1;  
            }
            wp++;
            lp++;
        }
        else
        {
            if (!wp)
                lp++;
            wp = wp - T[wp];
        }
        
    }
}

/*
 * 
 */
int main(int argc, char** argv) {
    freopen(FILE_IN, "r", stdin);
    freopen(FILE_OUT, "w", stdout);
    scanf("%s", word);
    wl = strlen(word);
    scanf("%s", line);
    ll = strlen(line);
    computeT();
    findMatches();
    printf("%d\n", mc);
    mc = MIN(mc, MAX_PRINT);
    for(i=0;i < mc;i++)
        printf("%d ", M[i]);
    return (EXIT_SUCCESS);
}