Cod sursa(job #315361)

Utilizator katakunaCazacu Alexandru katakuna Data 15 mai 2009 08:45:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
using namespace std;   
#include <cstdio>   
#include <string.h>   
#include <algorithm>   
  
#define Nmax 2000010   
  
int A, B, pi[Nmax], p, i, sol[1024];   
char a[Nmax], b[Nmax];   
  
void prefix(){   
  
    int p = 0, i;   
    for(i = 2; i <= A; i++){   
           
        while( p && a[p + 1] != a[i])   
            p = pi[p];   
           
        if( a[p + 1] == a[i] ){   
            p++;   
            pi[i] = p;   
        }   
           
    }   
  
}   
  
int main(){   
  
    FILE *f = fopen("strmatch.in", "r");   
    FILE *g = fopen("strmatch.out", "w");   
  
    a[0] = ' '; b[0] = ' ';   
    fscanf(f,"%s",a + 1);   
    fscanf(f,"%s",b + 1);   
    A = strlen(a) - 1; B = strlen(b) - 1;   
       
    prefix();   
       
    p = 0;   
    for(i = 1; i <= B; i++){   
           
        while( p && b[i] != a[p+1] )   
            p = pi[p];   
           
        if( b[i] == a[p+1] ){   
            p++;   
            if(p == A)   
                if(sol[0] <= 1000)   
                    sol[++sol[0]] = i - p;   
                else  
                    ++sol[0];   
        }   
           
    }   
       
    fprintf(g,"%d\n",sol[0]);   
    int M = min(sol[0], 1000);   
    for(i = 1; i <= M; i++)   
        fprintf(g,"%d ", sol[i]);   
       
    fclose(f);   
    fclose(g);   
       
    return 0;   
}