Cod sursa(job #1923671)

Utilizator virtualityBbbbbbbbbbbbbbbbbb virtuality Data 11 martie 2017 21:12:27
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<bits/stdc++.h>
#define N 2000020
using namespace std;
int  p[N], rs[N];
vector <int> s;
int main(){
    string a, b;
    int n, m, k=0;
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>b>>a;
    n=a.length();
    m=b.length();
    p[0]=0;
    int len=0, i=1, j, q=0;
      j=0;
    for(i=1;i<m;i++) {
        while(b[i]!=b[j] && j>0) j=p[j-1];
        if(b[i]==b[j])j++;
        p[i]=j;
    }
    j=0;
    for(i=0;i<n;i++){
        while(j>0 && a[i]!=b[j]){
                j=p[j-1];
        }
        if(a[i]==b[j])j++;
        if(j==m) s.push_back(i-m+1);
         
    }
    int k=min(s.size(), 1000);
    g<<s.size()<<endl;
    for(i=0;i<m;i++) g<<s[i]<<' ';
    return 0;
}