Pagini recente » Cod sursa (job #1944385) | Cod sursa (job #38835) | Cod sursa (job #2747255) | Cod sursa (job #2794826) | Cod sursa (job #2857932)
#include <bits/stdc++.h>
#define PatternSizeMax 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s;
int nxt[PatternSizeMax],n;
int sol[PatternSizeMax],nrsol;
void prep_pattern(string s)
{
nxt[0]=0;
int j=0,i=1;
while(i<n)
{
if(s[j]==s[i]) /// the characters are equal
{
nxt[i]=j+1;
j++;
}
else /// we search for a previous equal character (or the character at index 0)
{
while(s[j]!=s[i] && j>0)
j=nxt[j-1];
if(s[j]==s[i])
nxt[i]=j+1;
else nxt[i]=j;
}
i++;
}
}
void KMP()
{
char c;
int i=0,j=0;
/// we read the text character by character
while(fin>>c)
{
if(c==s[j]) /// we got pattern matched from 0 up to position j-1
j++;
else
{
while(c!=s[j] && j>0) /// we search for a previous character in pattern equal to c (or the character at index 0)
j=nxt[j-1];
if(c==s[j])
j++;
}
if(j==n) /// we got a match
{
sol[++nrsol]=i-j+1;
}
i++;
}
}
int main()
{
fin>>s;
n=s.length();
prep_pattern(s);
KMP();
fout<<nrsol<<'\n';
for(int i=1;i<=nrsol;i++)
fout<<sol[i]<<" ";
}