Cod sursa(job #884644)

Utilizator SerbanAlexandru9Serban Alexandru SerbanAlexandru9 Data 21 februarie 2013 09:42:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#define maxn 2000005
using namespace std;
char a[maxn],b[maxn];
int urm[maxn],m,n,nr;
vector <int> sol;
void cit(){
    FILE *f;
    f=fopen("strmatch.in","r");
    fgets(a,maxn,f);
    fgets(b,maxn,f);
    fclose(f);
    m=strlen(a);
    n=strlen(b);
    while((a[m-1]<'a'||a[m-1]>'z')&&(a[m-1]<'A'||a[m-1]>'Z')&&(a[m-1]<'0'||a[m-1]>'9'))
        m--;
    a[m]='\0';
    while((b[n-1]<'a'||b[n-1]>'z')&&(b[n-1]<'A'||b[n-1]>'Z')&&(b[n-1]<'0'||b[n-1]>'9'))
        n--;
    b[n]='\0';
}
void urmatorul(){
    int x,k;
    urm[0]=-1;
    k=-1;
    for(x=1;x<m;x++){
        while(k>=0&&a[x]!=a[k+1])
            k=urm[k];
        if(a[k+1]==a[x])
            k++;
        urm[x]=k;
    }
}
void kmp(){
    int i,k;
    k=-1;
    for(i=0;i<n;i++){
        while(k>=0&&a[k+1]!=b[i])
            k=urm[k];
        if(a[k+1]==b[i])
            k++;
        if(k==m-1){
            nr++;
            if(nr<=1000)
                sol.push_back(i-m+1);
            k=urm[k];
        }
    }
}
void afis(){
    FILE *f;
    f=fopen("strmatch.out","w");
    fprintf(f,"%d\n",nr);
    for(int i=0;i<nr&&i<1000;i++)
        fprintf(f,"%d ",sol[i]);
    fclose(f);
}
int main(){
    cit();
    urmatorul();
    kmp();
    afis();
    return 0;
}