Cod sursa(job #1087073)

Utilizator teoionescuIonescu Teodor teoionescu Data 18 ianuarie 2014 21:38:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000002;
string A,B;
int pi[Nmax];
int k;
int sol[1005],rasp;
int main(){
    in>>A>>B;
    for(int i=1;i<A.length();i++){
        while(k>0 && A[k]!=A[i]) k=pi[k-1];
        if(A[k]==A[i]) k++;
        pi[i]=k;
    }
    k=0;
    for(int i=0;i<B.length();i++){
        while(k>0 && A[k]!=B[i]) k=pi[k-1];
        if(A[k]==B[i]) k++;
        if(k==A.length()){
            if(rasp<1000) sol[++rasp]=i-A.length()+1;
            else ++rasp;
        }
    }
    out<<rasp<<'\n';
    for(int i=1;i<=(min(rasp,1000));i++) out<<sol[i]<<' ';
    return 0;
}