Cod sursa(job #1090744)

Utilizator kiralalaChitoraga Dumitru kiralala Data 23 ianuarie 2014 00:15:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005

using namespace std;
//CU KMP
FILE* f=freopen("strmatch.in","r",stdin);
FILE* o=freopen("strmatch.out","w",stdout);

char str[NMAX],sub[NMAX];
int n,m,num;
int pad[NMAX];
queue<int> sol;

void Reading()
{
    scanf("%s\n%s",sub,str);
    n=strlen(str);
    m=strlen(sub);
    sub[m]='#';
}
void InitPad()
{
    pad[0]=-1;
    int i=2,k=0;
    while(i<=m)
    if(sub[i-1]==sub[k])
        k+=1,pad[i]=k,i+=1;
    else if(k)
        k=pad[k];
    else
        pad[i]=0,i+=1;
}

int main()
{
    Reading();

    if(m>n) { printf("0"); return 0; }
    InitPad();

    int k=0;
    for(int i=0;k+i<n;)
    {
        if(str[k+i]==sub[i]) {
            if(i==m-1)
                { num+=1; if(num<1000) sol.push(k); }

            i+=1;
        }
        else {
            k+=i-pad[i];
            i=(pad[i]>-1)?pad[i]:0;
        }
    }

    printf("%d\n",num);
    while(!sol.empty()) { printf("%d ",sol.front()); sol.pop(); }

    return 0;
}