Cod sursa(job #977792)

Utilizator smaraldaSmaranda Dinu smaralda Data 26 iulie 2013 16:48:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#define NMAX 2000000
using namespace std;
vector <int> sol;

char a[NMAX+5],b[NMAX+5];
int pi[NMAX+5];

int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i,n,m,p;

    gets(a+1); n=strlen(a+1);
    gets(b+1); m=strlen(b+1);

    p=0;
    pi[1]=0;
    for(i=2;i<=n;i++) {
        while(p && a[i]!=a[p+1])
            p=pi[p];
        if(a[p+1]==a[i])
            p++;
        pi[i]=p;
        }

    p=0;
    for(i=1;i<=m;i++) {
        while(p && b[i]!=a[p+1])
            p=pi[p];
        if(a[p+1]==b[i])
            p++;
        if(p==n) {
            sol.push_back(i-n);
            p=pi[n];
            }
        }

    printf("%d\n",sol.size());
    for(i=0;i<sol.size() && i<1000;i++)
        printf("%d ",sol[i]);
    return 0;
}