Pagini recente » Cod sursa (job #1737437) | Cod sursa (job #1919859) | Cod sursa (job #2084496) | Cod sursa (job #1667016) | Cod sursa (job #2803421)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
/**
KMP[i] = lung celui mai lung prefix care este si sufix
**/
vector <int> KMP(string s){
s= "$"+s; /// adaugam un caracter
vector<int> pi( s.size() );
int k=0; /// k=pi[i-1]
for(int i=2; i<(int)s.size(); i++){
/// caz ideal s[i]==s[k+1]
while( k!=0 && s[i]!=s[k+1] ){
k=pi[k];
}
/// am gasit un match
if( s[i]==s[k+1] )
k++;
/// daca nu am gasit match => conform while k=0
pi[i]=k;
}
/// reindexam de la 0
pi.erase( pi.begin() );
return pi;
}
/**
Gaseste inceputul matchurilor lui s in t
s="abab"
t="ababcababab"
sol={ 0, 5, 7 };
**/
vector <int> FindMatches(string s, string t){
string to_kmp=s+"$"+t;
vector <int> kmp=KMP(to_kmp);
vector <int> ans;
for(int i=(int)s.size()+1; i<(int)kmp.size(); i++ ){
if( kmp[i]==(int)s.size() )
ans.push_back(i-2*(int)s.size());
}
return ans;
}
int main()
{
string s, t;
in>>s>>t;
vector <int> pi = FindMatches(s, t);
out<<(int)pi.size()<<'\n';
for( auto i:pi ){
if( i<1001 )
out<<i<<" ";
}
//for( auto i:pi)
//cout<<i;
return 0;
}