Pagini recente » Cod sursa (job #2833624) | Cod sursa (job #764669) | Cod sursa (job #2633328) | Cod sursa (job #3264467) | Cod sursa (job #219022)
Cod sursa(job #219022)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string s1,s2;
vector<int> v;
int pre[2000002];
void prefix(string s)
{
int l=s.length();
int k=0;
for(int i=2;i<l;i++)
{
while(k&&s[k+1]!=s[i])
k=pre[k];
if(s[k+1]==s[i])
k++;
pre[i]=k;
}
}
void kmp(string s1, string s2)
{
int l2=s2.length();
int l1=s1.length()-1;
int k=0;
for(int i=1;i<l2;i++)
{
while(k&&s1[k+1]!=s2[i])
k=pre[k];
if(s1[k+1]==s2[i])
k++;
if(k==l1&&v.size()<=1000)
v.push_back(i-l1);
}
}
void citire()
{
ifstream f("strmatch.in");
f>>s1>>s2;
f.close();
s1=" "+s1;
s2=" "+s2;
prefix(s1);
}
void scriere()
{
int l=v.size();
ofstream g("strmatch.out");
g<<l<<endl;
for(int i=0;i<l;i++)
g<<v[i]<<" ";
}
int main()
{
citire();
kmp(s1,s2);
scriere();
return 0;
}