Pagini recente » Cod sursa (job #2963047) | Cod sursa (job #2876307) | Cod sursa (job #2571638) | Cod sursa (job #1840537) | Cod sursa (job #3293069)
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int lps[2000001];
queue<int> q;
void LPS(string pattern)
{
int i=1;
int j=0;
int n=pattern.length();
while(i<n)
{
if(pattern[i]==pattern[j])
{
j++;
lps[i]=j;
i++;
}
else {
if(!j) {
lps[i]=0;
i++;
}
else {
j=lps[j-1];
}
}
}
}
void KMP(string pattern,string s)
{
int i=0,j=0;
while(i<s.length())
{
if(s[i]==pattern[j])
i++,j++;
if(j==pattern.length())
q.push(i-j),j=lps[j-1];
else
if(i<s.size() && s[i]!=pattern[j])
{
if(!j)
i++;
else
j=lps[j-1];
}
}
}
int main() {
string pattern,s;
getline(cin,pattern);
getline(cin,s);
LPS(pattern);
KMP(pattern,s);
cout << q.size() << endl;
int cnt=1000;
while(!q.empty() && cnt!=0)
{
cout << q.front() << ' ';
q.pop();
cnt--;
}
return 0;
}